Project Euler 69: Find the value of n ≤ 1,000,000 for which n/φ(n) is a maximum.

---

Project Euler 69 Problem Description

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.

Analysis

The totient function phi(n), also called Euler’s totient function, is defined as the number of positive integers <=n that are relatively prime to (i.e., do not contain any factor in common with) n, where 1 is counted as being relatively prime to all numbers. Since a number less than or equal to and relatively prime to a given number is called a totative, the totient function phi(n) can be simply defined as the number of totatives of n. For example, there are eight totatives of 24 (1, 5, 7, 11, 13, 17, 19, and 23), so phi(24)=8. We're trying to find the smallest φ(n) and the largest n in order to keep n/φ(n) at a maximum. For a prime p.

where the product is over the distinct prime numbers dividing n. And so it follows,

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.

This answers the problem, but finds only the first n to exceed our limit, L. There may, in fact, be many n that have the same ratio.

For example for L < 100, we would find the solution as 2 x 3 x 5 = 30, for a ratio of 3.75. But 60 and 90 also share this same ratio. A bit more challenging exercise would be to find the all the n that qualify within the range [1,100).

This program and method
solves all test cases
on HackerRank

Project Euler 69 Solution

Runs < 0.001 seconds in Python 2.7.
Use this link to get the Project Euler 69 Solution Python 2.7 source.

Afterthoughts

• for L=10⁷? 9,699,690 = 2 x 3 x 5 x 7 x 11 x 13 x 17 x 19, and following the same method for L=10⁹ is 223,092,870