Number Theory Optimization Required

Question

Given an integer n find smallest integer x such that φ(x) = n.

(10^5 < n < 10^8)

I know that lower bound for searching is n+1 and the upper bound is

n/((pow(e,0.577)*log(log(n))) + (3.0/(log(log(n)))))

Can you please provide any other method for doing the same .

Thanks.

Answer 1

Your question was migrated to stackexchange Mathematica. Please see the Mathematica implementation invphi.nb by Maxim Rytin, available at http://library.wolfram.com/infocenter/MathSource/696/ . This code easily handles integers n in your range.

See also Chapter 3 in A Course in Computational Number Theory by Bressoud and Wagon.