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.

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

We’re trying to find the smallest φ(n) and the largest n in order to keep n/φ(n) at a maximum. One method is to multiply as many consecutive primes as possible without exceeding the limit of 1,000,000.

Solution

Runs < 1 seconds in Python.

primes = [2,3,5,7,11,13,17,19,23,27,31,37,41]
limit=10**6
max = 1
for p in primes:
  if max * p > limit: break
  max *= p
print "Answer to PE69 = ", max

Comments

for 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 10⁹ would be 223,092,870