nerd's blog

inverse of euler's function
By nerd, 15 years ago, translation, In English

Please Help!


phi(N) = euler's function = x

how we can find N, when we are given x. let's name it like phi_inv(x) = N

for example: 

phi_inv(4) = 5, because phi(5) = 4.

x ≤ 1010
  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
15 years ago, hide # |
 
Vote: I like it -15 Vote: I do not like it
I don't know. It is really an interesting problem.
→ Reply
15 years ago, hide # |
← Rev. 4  
Vote: I like it 0 Vote: I do not like it
φ(4) = 2, φ(3) you find any solution or all solutions?

→ Reply
  • 15 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it
    I have solved this problem and find all answers if N <  = 1018 and used dp and factorization of N. But my classmates used brute-force with pruning and got AC ;)firstly need to determine what could be simpler in the decomposition of N.
    → Reply
    • 15 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it
      firstly, thanks!
      but, secondly, ii couldn't catch you as well, where is link to this problem and have you save all phi(i), where i = 1..1018 or something else. i couldn't catch you as well. could you be more specific?!
      → Reply
      • 15 years ago, hide # ^ |
        ← Rev. 2  
        Vote: I like it 0 Vote: I do not like it

        1. find all prime p satisfying n%(p - 1) =  = 0 
        2. sort all primes and run brute-force go(x), for every prime p bust α N = pα * q and run go(x / (pα - pα - 1))
        3. optimization many optimization
        → Reply
15 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it
is this problem from SPOJ (or Project Euler)?

write n in form of p_i ^ e_i, and we should have p_1 < p_2 < ... and e_1 >= e_2 >= ..., then factor n and use depth first search to get the answer?

i am not just sure i have solved the problem...
→ Reply