## Project Euler Problem #69

### May 21, 2010

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.

May 21, 2010 at 17:38

[…] done Problem 69 sometime ago but that was a fairly obvious non-programming solution. I’d taken a look at this […]

January 21, 2012 at 15:59

[…] actually worded quite straightforwardly, and a little thought showed that this was very similar to Problem #69 and Problem #70. The numerator in the resilience function is going to be the count of terms that […]