%I #21 Feb 16 2025 08:33:53

%S 2047,121,341,781,217,25,9,91,9,133,91,85,15,1687,15,9,25,9,21,221,21,

%T 169,25,217,9,121,9,15,49,15,25,545,33,9,35,9,39,133,39,21,451,21,9,

%U 481,9,65,49,25,49,25,51,9,55,9,55,25,57,15,481,15,9,529,9,33

%N Least strong pseudoprime to base n.

%C a(n)=9 if and only if n == 1 or 8 (mod 9). - _Robert Israel_, Mar 27 2018

%H Robert Israel, <a href="/A298756/b298756.txt">Table of n, a(n) for n = 2..10000</a>

%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/StrongPseudoprime.html">Strong Pseudoprime</a>

%H <a href="/index/Ps#pseudoprimes">Index entries for sequences related to pseudoprimes</a>

%p filter:= proc(n,b) local d,s,r;

%p if isprime(n) then return false fi;

%p s:= padic:-ordp(n-1,2);

%p d:= (n-1)/2^s;

%p if b &^ d mod n = 1 then return true fi;

%p for r from 0 to s-1 do

%p if b &^ (d*2^r) + 1 mod n = 0 then return true fi

%p od;

%p false

%p end proc:

%p f:= proc(b) local n;

%p for n from 9 by 2 do if filter(n,b) then return n fi od

%p end proc:

%p map(f, [$2..100]); # _Robert Israel_, Mar 27 2018

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

%o (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

%o a(n) = forcomposite(c=1, , if(is_a001262(c, n), return(c))) \\ _Felix Fröhlich_, Mar 28 2018

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

%K nonn

%O 2,1

%A _Amiram Eldar_, Jan 26 2018