login
A340749
Fermat weak pseudoprimes k to a base d, where d | k and 1 < d < k.
1
6, 10, 12, 14, 15, 18, 20, 21, 22, 26, 28, 30, 33, 34, 36, 38, 39, 42, 45, 46, 48, 50, 51, 52, 54, 55, 56, 57, 58, 62, 65, 66, 68, 69, 70, 72, 74, 75, 78, 80, 82, 84, 85, 86, 87, 90, 91, 93, 94, 95, 98, 100, 102, 105, 106, 110, 111, 112, 114, 116, 118, 120, 122
OFFSET
1,1
COMMENTS
Numbers k such that d^k == d (mod k) for some d with d|k and 1 < d < k.
Problem: what is the asymptotic density of the set of these numbers?
It seems that this sequence has an asymptotic density of 0.626... - Amiram Eldar, Jan 19 2021
LINKS
Thomas Ordowski, Density of Fermat weak pseudoprimes k to a base d, where d|k and 1<d<k, SeqFan mailing list, Jan 20 2021.
Carl Pomerance and Samuel S. Wagstaff, Jr., Some thoughts on pseudoprimes, Bulletin (Académie serbe des sciences et des arts, Classe des sciences mathématiques et naturelles, Sciences mathématiques), Vol. 46 (2021), pp. 53-72; arXiv preprint, arXiv:2103.00679 [math.NT], 2021; JSTOR link; author's link.
EXAMPLE
The number 6 is a term, because 6 | 3^6 - 3, wherein 3 | 6 and 1 < 3 < 6.
MATHEMATICA
q[n_] := CompositeQ[n] && AnyTrue[Rest @ Most @ Divisors[n], PowerMod[#, n, n] == # &]; Select[Range[120], q] (* Amiram Eldar, Jan 19 2021 *)
PROG
(PARI) isok(k) = fordiv(k, d, if ((d>1) && (d<k) && (Mod(d, k)^k == Mod(d, k)), return(1))); 0; \\ Michel Marcus, Jan 21 2021
CROSSREFS
Cf. A000790.
Sequence in context: A084227 A299992 A237051 * A296205 A325281 A100658
KEYWORD
nonn
AUTHOR
Thomas Ordowski, Jan 19 2021
STATUS
approved