|
|
A006970
|
|
Euler pseudoprimes: composite numbers n such that 2^((n-1)/2) == +-1 (mod n).
(Formerly M5442)
|
|
21
|
|
|
341, 561, 1105, 1729, 1905, 2047, 2465, 3277, 4033, 4681, 5461, 6601, 8321, 8481, 10261, 10585, 12801, 15709, 15841, 16705, 18705, 25761, 29341, 30121, 31621, 33153, 34945, 41041, 42799
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,1
|
|
COMMENTS
|
Pseudoprimes for the primality test from [Schick]: n odd is probably prime if (n-1) | A003558((n-1)/2). (Succeeds for 99.9975% of odd natural numbers less than 10^8.) - Jonathan Skowera, Jun 29 2013
Equivalently, these are composites n such that ((n-1)/2)^((n-1)/2) == +-1 (mod n). - Thomas Ordowski, Nov 28 2023
|
|
REFERENCES
|
R. K. Guy, Unsolved Problems in Number Theory, A12.
C. Schick, Weiche Primzahlen und das 257-Eck, 2008, pages 140-146.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
LINKS
|
|
|
MATHEMATICA
|
ok[_?PrimeQ] = False; ok[n_] := (p = PowerMod[2, (n - 1)/2, n]; p == Mod[1, n] || p == Mod[-1, n]); Select[2 Range[22000] + 1, ok] (* Jean-François Alcover, Apr 06 2011 *)
|
|
PROG
|
(PARI) isok(n) = {if (!isprime(n) && (n%2), npm = Mod(2, n)^((n-1)/2); if ((npm == Mod(1, n)) || (npm == Mod(-1, n)), print1(n, ", ")); ); } \\ Michel Marcus, Sep 12 2015
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
a(15) corrected (to 10261 from 10241) by Faron Moller (fm(AT)csd.uu.se)
|
|
STATUS
|
approved
|
|
|
|