1
$\begingroup$

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 ?

$\endgroup$
5
$\begingroup$

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$.

$\endgroup$
  • 1
    $\begingroup$ Did you mean $\lambda(p^\alpha)|k$ in your first sentence? $\endgroup$ – MichalisN Nov 12 '15 at 19:23
  • $\begingroup$ 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$ $\endgroup$ – Peter Nov 12 '15 at 19:25
1
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ A proof of this would be very interesting. $\endgroup$ – Peter Nov 12 '15 at 19:56
  • $\begingroup$ 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. $\endgroup$ – Peter Nov 12 '15 at 20:15
  • 1
    $\begingroup$ @Peter: You're absolutely right. I didn't check enough cases :) Hm. I will leave the answer but edit it to include your corrections. $\endgroup$ – MichalisN Nov 12 '15 at 20:40
  • 1
    $\begingroup$ 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$! $\endgroup$ – Peter Nov 13 '15 at 22:43
  • 1
    $\begingroup$ 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. $\endgroup$ – Peter Nov 13 '15 at 22:51

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.