Given an integer $y$, how can I find the biggest $x$, such that $\lambda(x)=y$, where $\lambda(x)$ is the Carmichael-function?
What is the inverse of the Carmichael-function?
-
0@Pete, I've posted a question about this issue. – 2011-06-03
1 Answers
The wiki article on the Carmichael function gives a bound that can be simplified to the statement that for all $x > x_0$, $\lambda(x) > \log(x)^{\log(\log(\log(x)))}$. So to find the largest x such that $\lambda(x)=y$, or to determine that none exists, check all values of $\lambda(x)$ for $x \le x_0$ or $\log(x)^{\log(\log(\log(x)))} \le y$. The only missing piece is the value of $x_0$. Unfortunately, I don't know. Wiki cites the bound from this paper:
Paul Erdős, Carl Pomerance, Eric Schmutz (1991) Carmichael's lambda function, Acta Arithmetica, vol. 58, 363–385.
The proof doesn't state a constant, and it relies on other asymptotics of the divisor function. I'll spend some more time on this later and if I find anything I'll add it to this answer. The other paper linked in the comments may also be worth looking at.
EDIT: If we replace the ineffective upper bound on the divisor function used by Erdős et al. with the inequality $d(y) \le y$, this yields $x \le (4 y)^{3 y}$. So to find the largest x such that $\lambda(x)=y$, or to determine that none exists, check all values of $\lambda(x)$ for $x \le (4 y)^{3 y}$.
EDIT: In the comments Gerry Myerson gives a tighter effective upper bound on the divisor function which can be used to create a more efficient algorithm by taking the size of $y$ into account.
-
0What I meant is "depending on an inequality with an unknown constant" which I think is the same as "ineffective" and the meaning of the o(1) term. I'll try to fix the ambiguity. – 2011-06-03