Raghu15_47's blog

Number Theory Problem
By Raghu15_47, history, 4 years ago, In English

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

  • Vote: I like it
  • +8
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
4 years ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

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 .

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +9 Vote: I do not like it

      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.

      → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    dhruv7888 Thanks man

    → Reply