Project Euler Problem 69 Solution

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$.

Values of $n$ and $\varphi(n)$
n	Relatively Prime	$\varphi(n)$	$n/\varphi(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, N. This reduces to simply finding the closest primorial to our limit and never having to calculate any totients; a time–consuming proposition.

Why Primorials?

For a positive integer $n$, its primorial, $n$#, is the product of the primes, starting from 2, that are not greater than $n$; that is, $${\displaystyle n\#=\prod _{p\leq n \atop p{\text{ prime}}}}$$ For example, 12# represents the product of those primes $\le 12$: $${\displaystyle 12\#=2\times 3\times 5\times 7\times 11=2310.}$$

Maximizing the Number of Distinct Prime Factors: By taking the product of consecutive primes starting from the smallest, we ensure that $ n $ has as many distinct prime factors as possible without exceeding the limit $ N $.

Minimizing $ \boldsymbol{\phi(n)} $: Each additional distinct prime factor $ p $ in $ n $ introduces a term $ \left(1 - \frac{1}{p}\right) $ in the product for $ \phi(n) $. Smaller primes have larger $ \left(1 - \frac{1}{p}\right) $ values, which means adding smaller primes more significantly reduces $ \phi(n) $, thereby increasing $n/\phi(n)$.

HackerRank version

Solves all test cases for Hackerrank Project Euler Problem 69

Find the value of $n < N$, (3 < N < 10^{18}) for which $n/φ(n)$ is maximum. In case of multiple answers, print the minimum.

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())):
    N = int(input())
    print(f(N))

Last Word

Solves bigger problems by adding more primes. What's listed here is fine for $10^{18}$.