A020229 Strong pseudoprimes to base 3.

121, 703, 1891, 3281, 8401, 8911, 10585, 12403, 16531, 18721, 19345, 23521, 31621, 44287, 47197, 55969, 63139, 74593, 79003, 82513, 87913, 88573, 97567, 105163, 111361, 112141, 148417, 152551, 182527, 188191, 211411, 218791, 221761, 226801

Offset: 1

Author

David W. Wilson

Keywords

• nonn

Links

• Charles R Greathouse IV, Table of n, a(n) for n = 1..24767 (first 752 terms from R. J. Mathar)
• Joerg Arndt, Matters Computational (The Fxtbook), section 39.10, pp. 786-792
• Eric Weisstein's World of Mathematics, Strong Pseudoprime
• Index entries for sequences related to pseudoprimes

Crossrefs

Cf. A001262, A072276, A056915, A074773, A005935.

Programs

Mathematica

sppQ[n_?EvenQ, ] := False; sppQ[n?PrimeQ, ] := False; sppQ[n, b_] := (s = IntegerExponent[n-1, 2]; d = (n-1)/2^s; If[PowerMod[b, d, n] == 1, Return[True], Do[If[PowerMod[b, d*2^r, n] == n-1, Return[True]], {r, 0, s-1}]]); A020229 = {}; lst = {}; k = 3; While[k < 500000, If[sppQ[k, 3], Print[k]; AppendTo[lst, k]]; k += 2]; lst (* Jean-François Alcover, Oct 20 2011, after R. J. Mathar *)

PARI

is_A020229(n,b=3)={ bittest(n,0) || return;ispseudoprime(n) && return;my(d=(n-1)>>valuation(n-1,2));Mod(b,n)^d==1 || until(n-1<=d*=2,Mod(b,n)^d+1 || return(1))} \\ M. F. Hasler, Jul 19 2012