nerd's blog

inverse of euler's function
By nerd, 14 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?
14 years ago, # |
  Vote: I like it -15 Vote: I do not like it
I don't know. It is really an interesting problem.
→ Reply
14 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it
φ(4) = 2, φ(3) you find any solution or all solutions?

→ Reply
  • 14 years ago, # ^ |
      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
    • 14 years ago, # ^ |
        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
      • 14 years ago, # ^ |
        ← 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
        • 14 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          OK, thanks. i will try. and can you give asymptotics.
          → Reply
          • 14 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            asympotic... i think O(log(n) * n1 / 3 * (verysmallvalue))
            → Reply
14 years ago, # |
  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