Let $λ(m)=n$ be the Carmichael Function of $m$. For each (even) number $n$, there is a largest number $m$ such that $λ(m)=n$. Let $C(n)$ denote the largest integer $m$ such that $λ(m)=n$. For instance, $C(2)=24$ and $C(4)=240$ since $24$ and $240$ are the largest numbers with Carmichael Function equal to $2$ and $4$ respectively. In these cases, $n$ is really small, and $C(n)$ is rather large compared to $n$. However for other $n$, $C(n)$ and $n$ are about the same size so there is no significant growth rate of $C(n)$ compared to $n$. Suppose this is not the case. So as $n$ gets larger and larger, is it possible that $C(n)$ will grow exponential compared to $n$? If not, what is the maximum growth rate of $C(n)$ compared to $n$?

  • $\begingroup$ Hmm, for the special case of $n$ being a power of $2$, the growth of $C(2^k)$ depends on the distribution of Fermat primes, and we don't even know if there are more than $5$ of those ... so this sounds pretty intractable. $\endgroup$ – Henning Makholm May 3 at 2:49
  • $\begingroup$ You could calculate a few values of $C(n)$ and then look it up in the Online Encyclopedia of Integer Sequences, oeis.org $\endgroup$ – Gerry Myerson May 3 at 3:56
  • 1
    $\begingroup$ See OEIS sequence A321712. $\endgroup$ – Robert Israel May 3 at 11:54

According to the Wikipedia page, there is a positive constant $c$ such that for sufficiently large $A$, there is $n > A$ with $\lambda(n) < (\ln A)^{c \ln \ln \ln A}$. That says if $m = \lambda(n)$, $C(m) \ge n > A$. Note that $$m = \lambda(n) < \exp(c (\ln \ln A)(\ln \ln \ln A)) < \exp(c (\ln \ln A)^2)$$ so $$C(m) > \exp(\exp(\ln(m)^{1/2}/c^{1/2}))$$ This is not quite as good as exponential growth, but I guess it is the best result known (or was at the time of writing).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.