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,1

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

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 *)

Prog

(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

Crossrefs

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

Sequence in context: A068264 A024021 A370685 * A145590 A241039 A278353

Adjacent sequences: A298753 A298754 A298755 * A298757 A298758 A298759

Keyword

nonn

Author

Amiram Eldar, Jan 26 2018

Status

approved