Python Implementation of Problem 70
View source code here on GitHub!
Includes
Problem Solution
Project Euler Problem 70
My time as a TA in the Discrete Mathematics class really paid off here
Problem:
Euler's totient function, $phi(n)$ [sometimes called the phi function], is used to determine the number of positive numbers less than or equal to $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, $phi(9)=6$.<br>The number $1$ is considered to be relatively prime to every positive number, so $phi(1)=1$.
Interestingly, $phi(87109)=79180$, and it can be seen that $87109$ is a permutation of $79180$.
Find the value of $n$, $1 lt n lt 10^7$, for which $phi(n)$ is a permutation of $n$ and the ratio $n/phi(n)$ produces a minimum.
1"""
2Project Euler Problem 70
3
4My time as a TA in the Discrete Mathematics class really paid off here
5
6Problem:
7
8Euler's totient function, $\\phi(n)$ [sometimes called the phi function], is used to determine the number of positive
9numbers less than or equal to $n$ which are relatively prime to $n$. For example, as $1, 2, 4, 5, 7$, and $8$, are all
10less than nine and relatively prime to nine, $\\phi(9)=6$.<br>The number $1$ is considered to be relatively prime to
11every positive number, so $\\phi(1)=1$.
12
13Interestingly, $\\phi(87109)=79180$, and it can be seen that $87109$ is a permutation of $79180$.
14
15Find the value of $n$, $1 \\lt n \\lt 10^7$, for which $\\phi(n)$ is a permutation of $n$ and the ratio $n/\\phi(n)$
16produces a minimum.
17"""
18from itertools import chain
19
20from .lib.primes import fast_totient
21
22
23def main() -> int:
24 answer = 0
25 ratio = float('inf')
26 stop = 10 ** 7
27 # restrict to 2k + 1, as 2 is a very common factor
28 # restrict to 3k ± 1, as 3 is a very common factor
29 # restrict to 6k ± 1, combining the above
30 for x in chain.from_iterable(zip(
31 range(6 - 1, stop, 30), # 6k - 1, x ≡ 1 (mod 5)
32 range(6 + 1, stop, 30), # 6k + 1, x ≡ 1 (mod 5)
33 range(6 + 5, stop, 30), # 6k - 1, x ≡ 2 (mod 5)
34 range(6 + 7, stop, 30), # 6k + 1, x ≡ 2 (mod 5)
35 range(6 + 11, stop, 30), # 6k - 1, x ≡ 3 (mod 5)
36 range(6 + 13, stop, 30), # 6k + 1, x ≡ 3 (mod 5)
37 range(6 + 17, stop, 30), # 6k - 1, x ≡ 4 (mod 5)
38 range(6 + 19, stop, 30) # 6k + 1, x ≡ 4 (mod 5)
39 )):
40 t = fast_totient(x)
41 strx = str(x)
42 strt = str(t)
43 if not all(strx.count(d) == strt.count(d) for d in set(strx)):
44 continue
45 nratio = x / t
46 if nratio < ratio:
47 answer = x
48 ratio = nratio
49 return answer