A298756 Least strong pseudoprime to base n.

2047, 121, 341, 781, 217, 25, 9, 91, 9, 133, 91, 85, 15, 1687, 15, 9, 25, 9, 21, 221, 21, 169, 25, 217, 9, 121, 9, 15, 49, 15, 25, 545, 33, 9, 35, 9, 39, 133, 39, 21, 451, 21, 9, 481, 9, 65, 49, 25, 49, 25, 51, 9, 55, 9, 55, 25, 57, 15, 481, 15, 9, 529, 9, 33

Offset: 2

Author

Amiram Eldar, Jan 26 2018

Keywords

• nonn

Comments

a(n)=9 if and only if n == 1 or 8 (mod 9). - Robert Israel, Mar 27 2018

Links

• Robert Israel, Table of n, a(n) for n = 2..10000
• Eric Weisstein's World of Mathematics, Strong Pseudoprime
• Index entries for sequences related to pseudoprimes

Crossrefs

Cf. A001262, A020229, A020230, A020231, A020232, A020233, A020234, A020235.

Programs

Maple

filter:= proc(n,b) local d,s,r;
  if isprime(n) then return false fi;
  s:= padic:-ordp(n-1,2);
  d:= (n-1)/2^s;
  if b &^ d mod n = 1 then return true fi;
  for r from 0 to s-1 do
    if b &^ (d*2^r) + 1 mod n = 0 then return true fi
  od;
false
end proc:
f:= proc(b) local n;
  for n from 9 by 2 do if filter(n,b) then return n fi od
end proc:
map(f, [$2..100]); # Robert Israel, Mar 27 2018

Mathematica

sppQ[n_?EvenQ, ] := False; sppQ[n?PrimeQ, ] := False; sppQ[n, b_] := Module[{ans=False},s = IntegerExponent[n-1, 2]; d = (n-1)/2^s; If[ PowerMod[b, d, n] == 1, ans=True, Do[If[PowerMod[b, d*2^r, n] == n-1, ans=True], {r, 0, s-1}]];ans];leastSPP[b_] := Module[{k=3}, While[ !sppQ[k,b],k+=2];k]; Table[leastSPP[n],{n, 2, 100}] (* after Jean-François Alcover at A020229 *)

PARI

is_a001262(n, a)={ (bittest(n, 0) && !isprime(n) && n>8) || return; my(s=valuation(n-1, 2)); if(1==a=Mod(a, n)^(n>>s), return(1)); while(a!=-1 && s--, a=a^2); a==-1} \\ after M. F. Hasler in A001262
a(n) = forcomposite(c=1, , if(is_a001262(c, n), return(c))) \\ Felix Fröhlich, Mar 28 2018