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.

Advertisements

2 Responses to “Project Euler Problem #69”


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


  2. […] 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 […]


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: