TheAlgorithms-Python

1
"""
2
Totient maximum
3
Problem 69: https://projecteuler.net/problem=69
4

5
Euler's Totient function, φ(n) [sometimes called the phi function],
6
is used to determine the number of numbers less than n which are relatively prime to n.
7
For example, as 1, 2, 4, 5, 7, and 8,
8
are all less than nine and relatively prime to nine, φ(9)=6.
9

10
n	Relatively Prime	φ(n)	n/φ(n)
11
2	1	                1	    2
12
3	1,2	                2	    1.5
13
4	1,3	                2	    2
14
5	1,2,3,4	            4	    1.25
15
6	1,5		            2	    3
16
7	1,2,3,4,5,6	        6	    1.1666...
17
8	1,3,5,7		        4	    2
18
9	1,2,4,5,7,8	        6	    1.5
19
10	1,3,7,9	            4	    2.5
20

21
It can be seen that n=6 produces a maximum n/φ(n) for n ≤ 10.
22

23
Find the value of n ≤ 1,000,000 for which n/φ(n) is a maximum.
24
"""
25

26

27
def solution(n: int = 10**6) -> int:
28
    """
29
    Returns solution to problem.
30
    Algorithm:
31
    1. Precompute φ(k) for all natural k, k <= n using product formula (wikilink below)
32
    https://en.wikipedia.org/wiki/Euler%27s_totient_function#Euler's_product_formula
33

34
    2. Find k/φ(k) for all k ≤ n and return the k that attains maximum
35

36
    >>> solution(10)
37
    6
38

39
    >>> solution(100)
40
    30
41

42
    >>> solution(9973)
43
    2310
44

45
    """
46

47
    if n <= 0:
48
        raise ValueError("Please enter an integer greater than 0")
49

50
    phi = list(range(n + 1))
51
    for number in range(2, n + 1):
52
        if phi[number] == number:
53
            phi[number] -= 1
54
            for multiple in range(number * 2, n + 1, number):
55
                phi[multiple] = (phi[multiple] // number) * (number - 1)
56

57
    answer = 1
58
    for number in range(1, n + 1):
59
        if (answer / phi[answer]) < (number / phi[number]):
60
            answer = number
61

62
    return answer
63

64

65
if __name__ == "__main__":
66
    print(solution())
67