Project Euler Problem #69

Read the details of the problem here

Summary

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

Solution

I started by creating a program that calculated totient values and displayed when it found maxima. It became evident that it simply was not going to scale to the scope of the problem. It did, however, given an obvious (in retrospect) insight into the problem.

The results that I got back from my program, before it essentially ground to a halt, were as follows:

n	φ(n)	n/φ(n)
2	1	2
6	2	3
30	8	3.75
210	48	4.375
2310	480	4.8125
30030	5760	5.213542

I recognised the values in n as the products of consecutive primes.

So, for instance, 30 = 2 * 3 * 5, 210 = 2 * 3 * 5 * 7. This meant that is was just a case of finding the maximum product of primes without exceeding the one million limit, which was the work of moments!

So the insight was, in order for the totient to be maximized, the number of primes making it up has to be maximized, so reducing considerably the number of relatively prime smaller numbers, hence the maxima was always to be found at these multiples.

Conclusion

Engage brain before typing code.

Advertisement