# What is the largest number $n$ with $\lambda(n)=k$ for a given $k$?

Let $k\ge 2$ be a natural number.

What is the largest number $n$ with $\lambda(n)=k$, where $\lambda(n)$ is the Carmichael-function. (See : https://en.wikipedia.org/wiki/Carmichael_function ) ?

For $k=2$, the maximum seems to be $24$.

For $k=4$, the maximum seems to be $240$.

For $k=6$, the maximum seems to be $504$.

For $k=60$, I found many $n's$, currently I arrived at $227,146,920$. (The program just found a higher number, so the number is not maximal)

I am not sure, but a maximum should exists for every $k$, thus defining the number $n(k)$.

Which growth rate will $n(k)$ probably have ? Exponential ?

Given $k$, the largest number $n$ with $\lambda(n)=k$ is the least common multiple of all prime powers $p^\alpha$ with $\lambda(p^\alpha)\mid k$. This can be found by simply enumerating the divisors of $n$ and seeing which ones are one less than a prime, together with a calculation for each prime dividing $n$. For example, the largest $n$ with $\lambda(n)=60$ is $$2^4 \cdot 3^2 \cdot 5^2 \cdot 7 \cdot 11 \cdot 13 \cdot 31 \cdot 61 = 6\text{,}814\text{,}407\text{,}600.$$

The "growth rate" of $n(k)$ is not well-defined, since some (indeed, most) integers $k$ are not a value of $\lambda$, and the ones that are will have wildly different sizes of $n(k)$. If you mean the maximal growth rate: presumably it is achieved when $k$ is highly composite. The product of all the divisors of $k$ is $k^{\tau(k)/2}$, which can be as large as $$\exp \bigg( \exp\bigg( \bigg( \frac{\log 2}2 + o(1) \bigg) \frac{\log k}{\log\log k} \bigg) \bigg);$$ presumably a fair share of these divisors are one less than a prime, and so this should be the approximate size of $n(k)$ as well; as you see, this is almost doubly exponential. Equivalently, there should exist numbers $n$ for which $\lambda(n)$ is as small as a constant times $\log\log n \log\log\log n$. This minimal order of $\lambda$ has been looked at seriously, and presumably there is a more precise conjecture out there somewhere.

If you like, a formula is $$n(k) = \prod_p p^{r(p,k)}, \quad\text{where }r(p,k)=\max\{r\ge0\colon \lambda(p^r)\mid k\}.$$ When $p\nmid k$, we have $r(p,k)$ equaling $0$ or $1$.

• Did you mean $\lambda(p^\alpha)|k$ in your first sentence? – MichalisN Nov 12 '15 at 19:23
• The primes in this example are $2,3,5,7,11,13,31,61$. Do I have to multiply the product of these always with $2k$, as here ? Please clarify this in the answer by giving a concrete formular. You can use $P$ for the primes with $p-1|k$ – Peter Nov 12 '15 at 19:25

This is not an answer but I can give a conjectural formula for $n$, lets denote it by $L(k)$. I recognized the first values you wrote as (up to sign) the coefficient of $q$ of the Eisenstein series $E_{k}$, so I tried to calculate the next. And indeed $L(8) = 480$. This suggested the formula $$L(k) = (-1)^{k/2}\frac{2k}{B_k}$$ where $B_k$ is the $k$-th Bernoulli number. However $2k/B_k$ is not always an integer. For example $2\cdot 12 / B_{12} = -65520/691$ but $L(12) = 65520$. So I conjecture $$L(k) = \text{numerator of } (-1)^{k/2}\frac{2k}{B_k}$$ The conjecture suggests $L(60) = 6814407600$ and indeed $\lambda(6814407600)=60$.

Edit: This conjecture is not correct as it is stated. For example $L(14) = 24$ but $\lambda(24) = 2$. However the counterexamples only occur when $k$ is not the Carmichael number of any integer. If there is an $n$ with $\lambda(n) = k$ then the conjecture above has been checked by Peter for $k\leq 40000$.

• A proof of this would be very interesting. – Peter Nov 12 '15 at 19:56
• For $k=14$ , I get $L(k)=24$, but $\lambda(24)=2$. There are many more counterexamples according to my PARI/GP program : $14,26,34,38,50,62,68,74,...$, but for some values, for example $100$, I get the right value for the Carmichael-function, but this does not mean the number given by the formula is maximal. – Peter Nov 12 '15 at 20:15
• @Peter: You're absolutely right. I didn't check enough cases :) Hm. I will leave the answer but edit it to include your corrections. – MichalisN Nov 12 '15 at 20:40
• Michalis's formula produces the same result as Greg Martin's formula (inculding the result that the carmichael number is wrong what means that there is no number $n$) upto at least $k=30,000$! – Peter Nov 13 '15 at 22:43
• I just finshed the search from $30,000$ to $40,000$ without finding a counterexample! So, for the even $k$ with $2\le k\le 40,000$ the "Bernoulli-formula" is correct. – Peter Nov 13 '15 at 22:51