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

[Tomasz Ordowski]

P.S. Professor Carl Pomerance further notes:
_________
The density of numbers du where d>1, u>1, d==1 (mod u)
is definitely smaller than 0.626, though I'm not sure
how much smaller.  For a fixed u the density is 1/u^2,
and the sum of all of these is pi^2/6 - 1.  But there is
overlap.  For example u=2 already handles all of the
cases when u == 2 (mod 4), so an upper bound for the
density of my subset is pi^2/6 - 1 - (1/4)(pi^2/8 - 1) < 0.587.
________
There are other families of positive density that would need to
be brought into play.  For example, say k=du where u is an odd
prime, d is a quadratic residue mod u and also d == 1 (mod (u-1)/2).
An example would be 28, where u = 7, d = 4.  I guess there are
also cubic residues to consider and so on.  With luck, this
process might converge.

==========================================
   I am grateful to him for these remarks and comments.
==========================================
T. Ordowski


śr., 20 sty 2021 o 15:09 Tomasz Ordowski <tomaszordowski at gmail.com>
napisał(a):

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