

A020236


Strong pseudoprimes to base 10.


4



9, 91, 1729, 4187, 6533, 8149, 8401, 10001, 11111, 19201, 21931, 50851, 79003, 83119, 94139, 100001, 102173, 118301, 118957, 134863, 139231, 148417, 158497, 166499, 188191, 196651, 201917, 216001, 226273, 231337, 237169, 251251, 287809, 302177
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,1


LINKS



EXAMPLE

9 is a strong pseudoprime to base 10. It's not enough to check that 10^8 = 1 mod 9. Since 8 = 1 * 2^3, we also need to verify that 10 = 1 mod 9 and 10^2 = 1 mod 9 as well. Since these are both equal to 1, we see that 9 is indeed a strong pseudoprime to base 10.
91 is also a strong pseudoprime to base 10. Besides checking that 10^90 = 1 mod 91, since 90 = 45 * 2, we also check that 10^45 = 1 mod 91; the 1 is enough to satisfy the definition of a strong pseudoprime.
99 is a Fermat pseudoprime to base 10 (see A005939) but it is not a strong pseudoprime to base 10. Although 10^98 = 1 mod 99, since 98 = 49 * 2, we have to check 10^49 mod 99, and there we find not 1 nor 1 but 10. Therefore 99 is not in this sequence. (End)


MATHEMATICA

strongPseudoprimeQ[b_, n_] := Module[{rems = Table[PowerMod[b, (n  1)/2^expo, n], {expo, 0, IntegerExponent[n  1, 2]}]}, (rems[[1]] == 1  MemberQ[rems, n  1]) && PowerMod[b, n  1, n] == 1]; max = 5000; Select[Complement[Range[2, max], Prime[Range[PrimePi[max]]]], strongPseudoprimeQ[10, #] &] (* Alonso del Arte, Aug 10 2018 *)


CROSSREFS



KEYWORD

nonn


AUTHOR



STATUS

approved



