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

[Tomasz Ordowski]

SUPPLEMENT

The last message from Professor Pomerance:

Tomasz,

I believe I can show these numbers have an asymptotic density.
I'm not sure how readily computable the density is.
I'll try and work this out.

Best,
Carl Pomerance


pt., 22 sty 2021 o 09:46 Tomasz Ordowski <tomaszordowski at gmail.com>
napisał(a):

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