algorithm - 需要数论优化

Question

给定一个整数 n 找到最小整数 x 使得 φ(x) = n。

(10^5 < n < 10^8)

我知道搜索的下限是n+1而上限是

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

您能否提供任何其他方法来做同样的事情。

谢谢。

Answer 1

您的问题已迁移到 stackexchange Mathematica。请参阅 Maxim Rytin 的 Mathematica 实现 invphi.nb，网址为http://library.wolfram.com/infocenter/MathSource/696/。此代码可以轻松处理您范围内的整数 n。

另见 Bressoud 和 Wagon 的《计算数论课程》第 3 章。