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.

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.

n Relatively Prime φ(n) n/φ(n)
2 1 1 2
3 1,2 2 1.5
4 1,3 2 2
5 1,2,3,4 4 1.25
6 1,5 2 3
7 1,2,3,4,5,6 6 1.1666…
8 1,3,5,7 4 2
9 1,2,4,5,7,8 6 1.5
10 1,3,7,9 4 2.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.

Posted by Kristian

19 comments

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

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

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.

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.

bit_cracker

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

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

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

Kristian

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.

Kristian

@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.

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.

Kristian

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

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;

Kristian

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.

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

Kristian

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.

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?

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

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

Kristian

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 Reply