[seqfan] Density of anti-Carmichael numbers

[Tomasz Ordowski]

Dear readers,

I have an interesting problem:

What is the asymptotic density of A121707 ?
See the last comment in https://oeis.org/history/view?seq=A121707&v=129

These are numbers k > 1 such that p-1 does not divide k-1 for every prime p
dividing k.
Odd numbers k > 1 such that k is coprime to the denominator of Bernoulli
B(k-1).
A number k > 1 is an anti-Carmichael if and only if gcd(k, b^k-b) = 1 for
some b.
For b = 2, we get similar numbers with slightly lower density.

Carl Pomerance:

I believe it's not hard to prove that this set has an asymptotic
density d with 0 < d < 1.  For each prime p let S_p denote the
set of n > p with n == p (mod p(p-1)).  So, each S_p has
density 1/(p^2 - p) and the union of the S_p's is the set of
composites that are not anti-Carmichael.  From this characterization,
it is possible to show that the density of the non-anti-Carmichaels
exists and is strictly between 0 and 1.  Also, an inclusion-exclusion
argument would allow one to compute the density to some precision
if one wished to do this.  For example, p=2 tells us that evens
are non-anti-Carmichael.  Then p=3 tells us that that the numbers
that are 3 mod 6 also can be thrown in, so we have density 2/3.
The 5 mod 20 numbers are also all odd and have density 1/20.
But they intersect 3 mod 6 in the set 45 mod 60, so the contribution
from p=5 is 1/20 - 1/60 = 1/30, and so using p=2,3,5 we have
density 7/10 for non-anti-Carmichaels.  In any event this process
converges rapidly.  For example, just from the above, we know the
non-anti-Carmichaels have density between 0.7 and 0.757

Amiram Eldar:

It seems that we can write a program to calculate the density based on
these hints - interesting!
How can these numbers be calculated efficiently?
Using the first k primes, for k=1..8 I am getting the following bound for
the density (if I was not wrong in my understanding of the process):
# primes density
1 0.5
2 0.333333
3 0.3
4 0.278571
5 0.272944
6 0.268648
7 0.266932
8 0.264810
Can it converge to what we see from the direct counts (~0.21 I think)?
The way I did the calculations up to the k=8 first primes was a "dumb" but
very simple calculation of counting the solution in the range of
LCM(p(i)*(p(i)-1), i-1..8) = LCM(2, 6, 20, 42, 110, 156, 272, 342)
= 232792560. I cannot go up and add p=17 because of the memory limit of my
computer. My feeling is that there must be a faster and elegant method to
do it properly.

Carl Pomerance:

To get the tail of the distribution beyond the first k primes,
one can get a lower estimate by summing 1/(p^2-p) for p running
over primes beyond the k-th prime.  For k = 8, the sum is < 0.011,
so from your calculation below, which I have not checked, the
density of the anti-Carmichael numbers is between 0.265
and 0.253.
In my prior email I was calculating the density of the complementary
set of non-anti-Carmichael numbers.  After the first 3 primes,
this set has density at least 0.7.  The sum of 1/(p^2-p) for
p starting at 7 (the 4th prime) is < 0.057.  So the non-anti-Carmichaels
have density between 0.7 and 0.757.
The inclusion-exclusion among the first k primes is not completely
straightforward, and as I wrote, I haven't checked that you did
it correctly below.  Let me try now for k=4 to see if we agree.
The residue class 7 mod 42 is completely disjoint from 3 mod 6,
so we need only consider the interaction of it with 5 mod 20.
This is the residue class 385 mod 420, so the contribution of
7 to the non-anti-Carmichaels is 1/42 - 1/420 = 3/140.  Hence
using k=4, the non-anti-Carmichaels have density at least
7/10 + 3/140 = 101/140, so the anti-Carmichaels have density
at most 39/140 = 0.27857... .  This agrees with Eldar.

Maybe someone will use these ideas better.

Best regards,

Thomas Ordowski
____________________
https://oeis.org/A121707
https://oeis.org/A121707/a121707_1.pdf
https://oeis.org/A267999 and https://oeis.org/A306097