### Raghu15_47's blog

By Raghu15_47, history, 3 years ago,

Need help with this number theory problem. Give me some hints, please.

Problem

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

• +8

| Write comment?
 » 3 years ago, # | ← Rev. 2 →   +10 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 .
•  » » 3 years ago, # ^ |   0 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.
•  » » » 3 years ago, # ^ |   +9 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.
•  » » 3 years ago, # ^ |   +3 dhruv7888 Thanks man