Project Euler Problem 69 Solution: Totient maximum

Project Euler Problem 69 Statement

Euler's Totient function, $\varphi(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, $\varphi(9)=6$.

n	Relatively Prime	PHI(n)	n/PHI(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 $\frac{n}{\varphi(n)}$ for $n\le 10$.

Find the value of $n\le 1,000,000$ for which $\frac{n}{\varphi(n)}$ is a maximum.

Solution

The totient function $\varphi(n)$, also known as Euler's totient function, is defined as the number of positive integers less than or equal to $n$ that are relatively prime to $n$. Two numbers are relatively prime if they share no common factors other than 1. By definition, 1 is considered relatively prime to all numbers. The integers that are both less than or equal to $n$ and relatively prime to $n$ are called totatives of $n$.

For example, for $n=24$, the totatives are $\{ 1, 5, 7, 11, 13, 17, 19, 23 \}$, so $\varphi(24) = 8$.

Our goal is to maximize the ratio $\frac{n}{\varphi(n)}$ for $n\le 10^6$. This involves understanding the formula for $\varphi(n)$, which is derived from the prime factorization of $n$:

$$\varphi(n) = n\prod\limits_{p|n} (1-\frac{1}{p})$$

where the product is taken over all distinct prime numbers $p$ that divide $n$. From this, the ratio becomes:

$$\frac{n}{\varphi(n)} = \prod\limits_{p|n} \frac{p}{p-1}$$

Our method solves this problem by multiplying distinct, consecutive primes starting from 2 until we reach, but do not exceed, the limit, L, of 1,000,000. This reduces to simply finding the closest primorial to our limit and never having to calculate any totients; a time–consuming proposition.

HackerRank version

Solves all test cases for Hackerrank Project Euler Problem 69

HackerRank Project Euler 69 increases the limit to 10¹⁸.

Python Source Code

def f(N):
    maxn = 1
    for p in primes:
        if maxn*p >= N: return maxn
        maxn *= p
    return None

primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53]
for _ in range(int(input())):
    print(f(int(input())))

Last Word

Solves bigger problems by adding more primes.