problem 69 in julia

1 files changed, 54 insertions, 0 deletions

diff --git a/julia/069-totient_maximum.jl b/julia/069-totient_maximum.jl
new file mode 100644
index 0000000..fc775cb
--- /dev/null
+++ b/julia/069-totient_maximum.jl
@@ -0,0 +1,54 @@
+###
+# Totient maximum
+# Problem 69
+#
+# Euler's Totient function, φ(n) [sometimes called the phi function], is used to determine
+# the number of numbers less than n which are relatively prime to n. For example, as 1, 2,
+# 4, 5, 7, and 8, are all less than nine and relatively prime to nine, φ(9)=6.
+# n
+# Relatively Prime
+# φ(n)
+# n/φ(n)
+# 2  | 1           | 1 | 2
+# 3  | 1,2         | 2 | 1.5
+# 4  | 1,3         | 2 | 2
+# 5  | 1,2,3,4     | 4 | 1.25
+# 6  | 1,5         | 2 | 3
+# 7  | 1,2,3,4,5,6 | 6 | 1.1666...
+# 8  | 1,3,5,7     | 4 | 2
+# 9  | 1,2,4,5,7,8 | 6 | 1.5
+# 10 | 1,3,7,9     | 4 | 2.5
+# It can be seen that n=6 produces a maximum n/φ(n) for n ≤ 10.
+# Find the value of n ≤ 1,000,000 for which n/φ(n) is a maximum.
+###
+
+
+# euler product formula: https://en.wikipedia.org/wiki/Euler%27s_totient_function#Euler's_product_formula
+# https://cp-algorithms.com/algebra/phi-function.html
+
+# where p is prime:
+# rule 1: ϕ(p)   = p - 1
+# rule 2: ϕ(p^k) = p^k - p^(k - 1)    k - 1 is the number of times p^k is divisible by p
+#                                     (exploit powers factors, same reason we can stop at √n when checking for prime)
+#
+# where a and b a relativly prime
+# rule 3: ϕ(ab)  = ϕ(a)ϕ(b)
+
+
+function totient_sieve(n)
+    totients = Array(1:n)
+    # if number is composed of multiple primes we use rule 3 to apply rule 2 multiple times
+    for i in 2:n
+        if totients[i] == i  # only enter for prime since other number were previously subtracted
+            for j in i:i:n   # iterate over primes powers (see rule 2 above)
+                totients[j] = totients[j] - totients[j] ÷ i
+            end
+        end
+    end
+    return totients
+end
+
+
+result = argmax([i / t for (i, t) in enumerate(totient_sieve(1_000_000))])
+
+println(result)