CODEWITHSUNDEEP
algorithmnumber-theory
Purva Gupta
Purva Gupta

Reputation: 115

Number Theory Optimization Required

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.

Upvotes: 0

Views: 235

Answers (1)

KennyColnago
KennyColnago

Reputation: 299

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.

Upvotes: 1

Related Questions