Python Implementation of Problem 69
View source code here on GitHub!
Includes
Problem Solution
Project Euler Problem 69
First I brute forced to see if I noticed a pattern. Having noticed one, I implemented it as a solution and found it to be the right answer.
Problem:
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.
1"""
2Project Euler Problem 69
3
4First I brute forced to see if I noticed a pattern. Having noticed one, I implemented it as a solution and found it to
5be the right answer.
6
7Problem:
8
9Euler's Totient function, φ(n) [sometimes called the phi function], is used to determine the number of numbers less than
10n 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
11nine, φ(9)=6.
12
13n Relatively Prime φ(n) n/φ(n)
142 1 1 2
153 1,2 2 1.5
164 1,3 2 2
175 1,2,3,4 4 1.25
186 1,5 2 3
197 1,2,3,4,5,6 6 1.1666...
208 1,3,5,7 4 2
219 1,2,4,5,7,8 6 1.5
2210 1,3,7,9 4 2.5
23
24It can be seen that n=6 produces a maximum n/φ(n) for n ≤ 10.
25
26Find the value of n ≤ 1,000,000 for which n/φ(n) is a maximum.
27"""
28from .lib.primes import primes
29
30
31def main() -> int:
32 answer = 1
33 for p in primes():
34 new = answer * p
35 if new <= 1_000_000:
36 answer = new
37 else:
38 break
39 return answer