Problems & Puzzles: Conjectures

Conjecture 75. Sebastian's formula for a special case of the Carmichael function.

In 2009 Sebastián Martín Ruiz empirically got a formula for the Carmichael Function λ(n), when n is the factorial n!.

You can see the Sebastian's formula here as formula (4):

λ(n!) = 1 if n=1 or n=2
          2 if n=3
          4 if n=5
          n!/(2*n#) otherwise, n# is the greatest primorial pk# such that pk<=n

Since 2009 neither Sebastián nor several mathematicians asked to do it, have proved the empirical formula. Sebastián accepts that he has confirmed his formula only up to n=3000!, comparing the values produced by his formula against these from the built-in Mathematica's function CarmichaelLambda[n].

Q1. Perhaps you would like to extend the range of confirmation beyond n=3000!
Q2. Or perhaps you would like better to prove the Sebastián's formula
Q3. Do you know some other important number theory functions involving both factorial and primorial functions?

Contributions came from Emmanuel Vantieghem, Giovanni Resta and Dmitry Kamenetsky.


The three contributors sent a formal proof of this Conjecture. Emmanuel and Dmitry sent their respective proof in pdf files attached here: 1 and 2.

Giovanni sent his proof in plain text, shown below:

For what concerns Conjecture 75, the proof is trivial and follows
immediately from the formula for the function.

As stated in Wikipedia, the function lambda (L) of Carmichael
can be computed using the fact that

L(2^e) =  phi(2^e)/2 = (1/2)*2^(e-1)  (for e>2)
L(p^e) =  phi(p^e) = (p-1)*p^(e-1),  for p prime.

and then, if n = p^a * q^b * r^c *... L(n) can be
computed taking the least common multiple of the Lambda's
of the prime powers of n:

L(n) = LCM( L(p^a), L(p^b), L(r^c), ....)

From this it follows immediately that, for n>4, if

n! = 2^a * 3^b * 5^c * 7^d * ....
L(n!) = LCM( (1/2) 2^(a-1),  (3-1)3^(b-1),  (5-1) 5^(c-1), .... )

So, we are sure that in the factorization of the LCM there are all the
terms (1/2) 2^(a-1), 3^(b-1), 5^(c-1) and so on, since they are
prime to each other. On the contrary, we can see that the various term (3-1), (5-1), (7-1) and so on, have no influence, since the prime factors in each term (p-1) have exponents which are at most equal to the various exponents (a-1), (b-1), (c-1) and so on.

Indeed, a problem can arise only if a certain p-1 is divisible by
z^k where z is a prime, and n! is divisible by z^h and
k >= h so that the term in the LCM (z-1)z^(h-1) is not sufficient
to account for z^k. But this (k >= h) is impossible. Because
if  p-1 = f*z^k (where f>1, because p-1 is even).
Then  f*z^k < n and this means that up to n there are at least f*z^(k-1)
terms divisible by z, so (it is easy to see) that the exponent of z in n! cannot be smaller than k. For example, if p=23 and p-1=22 = 2*11
in n! there are at least 2 factors (11 and 22) divisible by 11, so
n! contains at least a factor 11^2 and so in the LCM there is already
a term  (11-1)*11^(2-1), so 23-1 is already accounted for.

So we can disregard all the terms (p-1) and thus the LCM is simply
the product and we have:

L(n!) = (1/2)  * 2^(a-1) * 3^(b-1) * 5^(c-1) * 7^(d-1) * ..

but this, for n>4, is exactly  equal to n! / (2 * n#), because
there is a factor (1/2) and there is a factor (1/p) for each
prime p<=n.



Q3. Emanuel wrote on May 3, 2015, the following proof.



Records   |  Conjectures  |  Problems  |  Puzzles