Explain the maths of this to me please.

[stuart]

So, I was doing some Project Euler.

I got the solution via my program but it took about 2 hours to run since it was a brute force solution.

However, once you solve the problem you can access the thread for that problem and see other people solutions. There solutions were dead simple but I don't understand the maths of why it works.

Here's the puzzle:

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.

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.

The solutions that other people used was 2*3*5*7*11*13*17 (basically the product of all the primes so that the result is less than 1,000,000.

Why is that the solution ?

 

[Master_Ghost_Knight]

This is a bit unfamiliar ground to me. I have been working in something similar, but here is the jits of it.
For any number x, every number y>x/2 is a co-prime
We don't actualy know the analitic function φ(n), but given the previous fact it should be something of the sort: (which you an analyse in terms of magnitude)
φ(n)=0.5*n+f(n)
with f(n)=0.5*n-n_of_not_co-primes.
So n/φ(n) should be something like: 1/(0.5+f(n)/n) or 1/(1-n_of_not_co-primes/n)
So we transformed the problem of maximizing n/φ(n) to minimizing f(n)/n, or maximizing n_of_not_co-primes/n. Now a number which sequencialy acounts for all primes until a certain point, is the smalest number with "m" prime factors which eliminates most of the non-co-prime numbers from the list, because every prime factor and every non repetitive combination of those factors is not a co-prime. Had it not been sequential and "n" would be a bigger number and therefor n_of_not_co-primes/n smaller. Had all the factors not been different and you can't max out the number of different combinations, and now here is the part where i am not sure, is the decrease of possible combinations "due to the fact that you have repeated a number or the supression of factors" bigger then the decrease of n? If the answer is yes then the answer is correct, if it is no then it is not correct and it just happened to be a coincidence (which happens allot in prime factorizations).
Sory I can't help you more than that.

 

[Pulsar]

As is shown on the wiki page of the totient function, the following equation is valid:

where the right-hand side means the product of all factors (1-1/p), for which p is a prime divisor of n. So when is this product minimal?

The smaller the value of a prime divisor p, the smaller the factor (1-1/p).
The more prime divisors n has, the more factors the product has.
Every factor is < 1, so the more factors, the lower the entire product is.

Combining these remarks, you can see that the product will be minimal if n is the product of the lowest distinct primes.