Totient maximum

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.

Idea

Want $ n / \phi(n) $ bigger, need $ n $ bigger and $ \phi(n) $ smaller.

It is easy to notice that $ n / \phi(n) \ge 2 $ for $ n $ is even. So we guess the result is even.

And we also notice that if $ n $ has more distinctive odd prime factors, it will remove more 'possible' relatively prime, whic makes $ \phi(n) $ smaller.

So the solution is to get an even number which has most distinctive odd prime factors.

In [1]:
def get_prime_factors(n):
    d = 2
    factors = []
    while pow(d, 2) <= n:
        while n % d == 0:
            n //= d
            factors.append(d)
        d += 1
    if n != 1:
        factors.append(n)
    return factors
In [2]:
get_prime_factors(8)
Out[2]:
[2, 2, 2]
In [3]:
get_prime_factors(5)
Out[3]:
[5]
In [4]:
get_prime_factors(24)
Out[4]:
[2, 2, 2, 3]
In [5]:
def get_odd_prime_factors(n):
    prime_factors = get_prime_factors(n)
    return list(filter(lambda i: i % 2 == 1, set(prime_factors)))
In [6]:
get_odd_prime_factors(12)
Out[6]:
[3]
In [7]:
get_odd_prime_factors(90)
Out[7]:
[3, 5]
In [8]:
def solve(upper_bound):
    max_result = (0, 0)
    for i in range(6, upper_bound+1, 6):
        odd_prime_factors = get_odd_prime_factors(i)
        max_result = max(max_result, (i, len(odd_prime_factors)), key=lambda r: r[1])
    return max_result
In [9]:
solve(10)
Out[9]:
(6, 1)
In [10]:
solve(int(1e6))
Out[10]:
(510510, 6)