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 functools import reduce
19from itertools import chain
20
21from .lib.primes import prime_factors
22
23
24def totient(n: int) -> int:
25 return reduce(lambda x, y: x * (y - 1), prime_factors(n), 1)
26
27
28def main() -> int:
29 answer = 0
30 ratio = float('inf')
31 stop = 10 ** 7
32 # restrict to 2k + 1, as 2 is a very common factor
33 # restrict to 3k ± 1, as 3 is a very common factor
34 # restrict to 6k ± 1, combining the above
35 for x in chain.from_iterable(zip(
36 range(6 - 1, stop, 30), # 6k - 1, x ≡ 1 (mod 5)
37 range(6 + 1, stop, 30), # 6k + 1, x ≡ 1 (mod 5)
38 range(6 + 5, stop, 30), # 6k - 1, x ≡ 2 (mod 5)
39 range(6 + 7, stop, 30), # 6k + 1, x ≡ 2 (mod 5)
40 range(6 + 11, stop, 30), # 6k - 1, x ≡ 3 (mod 5)
41 range(6 + 13, stop, 30), # 6k + 1, x ≡ 3 (mod 5)
42 range(6 + 17, stop, 30), # 6k - 1, x ≡ 4 (mod 5)
43 range(6 + 19, stop, 30) # 6k + 1, x ≡ 4 (mod 5)
44 )):
45 t = totient(x)
46 strx = str(x)
47 strt = str(t)
48 if not all(strx.count(d) == strt.count(d) for d in set(strx)):
49 continue
50 nratio = x / t
51 if nratio < ratio:
52 answer = x
53 ratio = nratio
54 return answer