Need help with this number theory problem. Give me some hints, please.
Given an integer N <= 10^40 find the smallest m <= N such that m/phi(m) is maximum. Where phi is Euler's totient function.
Input:
The first line in the input gives the number of test cases T (T<=200), and then T lines follow each containing an integer N.
Output: Output the smallest required value of m.
Sample Input:
1 10
Output: 6
phi(m) is m*(1-1/P1)*(1-1/P2)*(1-1/Pn) for m=(P1^A1)*(P2^A2).....(Pn^An), so m/phi(m)=1/((1-1/P1)*(1-1/P2)*(1-1/Pn))=P1*P2...Pn/((P1-1)*(P2-1)*....(Pn-1)) . Which is maximum for minimum value of every Pi and you can see that it is always increasing as X>X-1 so X/(X-1) >1 , Now log2(10^40)=132.87 so you need to find first 133 prime no. And multiply them until the value of there multiplication is less than given N . N=1 is an exception for which the answer is 1 .
why does the optimal answer has the first k prime numbers whose product<=N , why can't we take some subset of primes whose product<=N but they are not the smallest ones. the X>X-1 proof doesn't seem to be correct.
The evaluated value of m/m/phi(m)=1/((1-1/P1)*(1-1/P2)*(1-1/Pn))=P1*P2...Pn/((P1-1)*(P2-1)*....(Pn-1)). So, each term in this product being X/(X-1) which can be written as (1+1/(X-1)) which decreases with X, so to maximize our product, we need to choose the primes from starting.
dhruv7888 Thanks man