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

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

Written by on 5 November 2011

Topics: Project Euler

We are changing topics again to a more classical number theory problem with Problem 69 of Project Euler. The problem is about factoring and reads

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.

nRelatively Primeφ(n)n/φ(n)
2112
31,221.5
41,322
51,2,3,441.25
61,523
71,2,3,4,5,661.1666…
81,3,5,742
91,2,4,5,7,861.5
101,3,7,942.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.

My first thought was to reuse some of the old problems which dealt with factoring. Problem 12 was a pretty good candidate for this. However before I got that far I realised two things. First of all a number need not be a factor to not be relatively prime, so that renders the idea useless. The other fact is that if the number n divisible by 2 then every number which is also divisible by two cannot be relatively prime to n. Same thing goes for 3. Once we reach an n divisible by 4 we will see that it is not relatively prime to any even number since they share 2 as a common prime factor. So it seems that in general the more distinct prime factors n has, the smaller φ(n) must be and the larger the ratio had to be. So where will that lead us?

Looking at wikipedia’s definition for Euler’s totient function it says

So basically that means we are trying to maximize the following function

That means making the denominator as small as possible. This will happen for the number with the most  distinct small prime factors. So we should be able to construct it by multiplying primes until we reach the largest number less then 1.000.000.

Since we already countless of times have made a prime generating function, the problem is mainly trivial from here on. The code can be implemented as

int result = 1;
int[] primes = ESieve(2, 200);
int i = 0;
int limit = 1000000;

while(result* primes[i] < limit){
    result *= primes[i];
    i++;
}

It runs in 0ms and spits out the result

The number with the maximum ratio is 510510
Solution took 0 ms

Wrapping up

This problem was pretty easy to solve once we go got the definition unwrapped. Otherwise generating all divisors of each number less than a million would have been a huge computational task.

As usual you can find the source code here.

19 Comments For This Post I'd Love to Hear Yours!

  1. anonymous says:

    actually, there is an even faster way which is to use your calculator. 2*3*5*7*11*13*17

  2. Kristian says:

    Yes that would work for this particular solution, but it is kind of guess work.

  3. Khaur says:

    There’s a typo in the totient function formula, it should be a ‘p’ instead of a ‘n’ in the denominator, and later we’re trying to minimise the denominator, not maximise it. It’s not that hard to see what you meant, but it was a bit confusing on first read. Also I guess you should point to http://en.wikipedia.org/wiki/Totient instead of Euler’s page which barely mentions the totient function (nowadays at least).

    I feel kind of dumb now, because I skipped over the formula straight to the multiplication property and I used prime factorisation to brute force the problem.

  4. Kristian says:

    Hi Khaur

    Thanks for spotting those things. It is fixed now I think. I have kept the link, as that points to the same thing as you point to.

  5. bit_cracker says:

    what will be the logic when we have to minimize this ratio and N<=10^18 ?

  6. Upen says:

    Hello sir , What to do if want to find maximum value of n for which φ(n)/n is maximum..

  7. Upen says:

    Sir, What to do for finding maximum value of n for which φ(n)/n is maximum.?

  8. Kristian says:

    The number is 1 for every prime number, which is the minimum value as far as I remember. So the minimization problem is solved by choosing any prime.

  9. Kristian says:

    @upen The number will increase as the n increases. So there is no maximum I think. And if you put an upper bound on it, then you already have the code as described.

  10. Upen says:

    Yeah we have upper bound say n .. we have to find value of i for which φ(i)/i is maximum where i may be between 2 to n.

  11. Kristian says:

    I didn’t see you had switched the fraction. In that case any prime number will do and the ration will be one.

  12. Upen says:

    what do you mean by any prime number will do. can you please write the code for finding this .
    For.Ex. Suppose we have find the maximum φ(i)/i for n = 5 , n = 6 , n = 10;
    for n = 5;
    we have to find max(φ(2)/2, φ(3)/3, φ(4)/4, φ(5)/5);
    for n = 6;
    we have to find max(φ(2)/2, φ(3)/3, φ(4)/4, φ(5)/5, φ(6)/6);
    for n = 10;
    we have to find max(φ(2)/2, φ(3)/3, φ(4)/4, φ(5)/5, φ(6)/6,φ(7)/7,φ(8)/8,φ(9)/9,φ(10)/10);

    How to optimize this if we have n <= 10^18;

  13. Kristian says:

    Funny that there are two people asking the same. It sounds to me like a homework assignment.

    I have already given you a hint, so I will let you figure it out from here. However, I can give you another hint. The explanation lies in the definition of eulers totient function.

  14. Upen says:

    I did not find any explanation any where , Please explain it clearly .

  15. Kristian says:

    Nope, I will only give you the hint that you need to understand Euler’s totient function. If you understand that you will also understand the answer to your question.

  16. Sam says:

    I think that the answer to minimize it would be the greatest prime number less than or equal to n. The idea now is how to find this prime number or at least a very close number to it. Right?

  17. Upen says:

    Yeah you are right do you have any idea about finding a largest prime number less than given number.

  18. sanjeev says:

    Why are u generating Sieve between ESieve(2,200).

  19. Kristian says:

    Because I have found that I am looking for a number which has a prime factorization with as many different primes as possible. Once I multiply all primes less than 200 I reach beyond the limit given in the problem.

Leave a Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

Notify me of comments via e-mail. You can also subscribe without commenting.