[seqfan] Density of Fermat weak pseudoprimes k to a base d, where d|k and 1<d<k

[Tomasz Ordowski]

Dear readers!

Let's define exactly:

Numbers k for which d^k == d (mod k) to some d such that d|k and 1<d<k.

Problem: What is the asymptotic density of the set of these numbers?

See my new draft: https://oeis.org/draft/A340749
https://oeis.org/history/view?seq=A340749&v=17

It seems that this sequence has an asymptotic density of 0.626...
based on this count of terms k not exceeding 10^n:
n #k
1 2
2 52
3 591
4 6169
5 62389
6 625941
7 6265910
8 62677099
[Amiram Eldar]

Best regards,

Thomas
_____________
Carl Pomerance wrote to me about this as follows:

Tomasz,

Maybe one can show the density exists.  For example,
if k = 2^a m, with m == 1 (mod 2^a), then d=m works
(assuming a > 0, m > 1).
Similarly, if k = 3^a m, with m == 1 (3^a), then d=m
works.
Together these two possibilities cover density 5/12
of all numbers.

There may be other similar families.

A former student of mine, Shuguang Li, showed that
the case of d fixed is rare.  This is unpublished, and
I think he only did d=2.

Anyway, a nice problem.

Best,
Carl
____________
More generally, if k is of the form du where gcd(d,u)=1
and d == 1 (mod u), then d^k == d == 1 (mod u) and
d^k == d == 0 (mod d), so d^k == d (mod k).

I suppose it would not be so hard to work out the density
of all such numbers k = du as above.  Maybe it is about .626.

Best,
Carl