A340749 Fermat weak pseudoprimes k to a base d, where d | k and 1 < d < k.

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

Author

Thomas Ordowski, Jan 19 2021

Keywords

• nonn

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

Examples

			The number 6 is a term, because 6 | 3^6 - 3, wherein 3 | 6 and 1 < 3 < 6.
		

Links

• Amiram Eldar, Table of n, a(n) for n = 1..10000
• Thomas Ordowski, Density of Fermat weak pseudoprimes k to a base d, where d|k and 1, 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.

Crossrefs

Cf. A000790.

Programs

Mathematica

q[n_] := CompositeQ[n] && AnyTrue[Rest @ Most @ Divisors[n], PowerMod[#, n, n] == # &]; Select[Range[120], q] (* Amiram Eldar, Jan 19 2021 *)

PARI

isok(k) = fordiv(k, d, if ((d>1) && (dMichel Marcus, Jan 21 2021