cp's OEIS Frontend

A298756 Least strong pseudoprime to base n.

%I A298756 #21 Feb 16 2025 08:33:53
%S A298756 2047,121,341,781,217,25,9,91,9,133,91,85,15,1687,15,9,25,9,21,221,21,
%T A298756 169,25,217,9,121,9,15,49,15,25,545,33,9,35,9,39,133,39,21,451,21,9,
%U A298756 481,9,65,49,25,49,25,51,9,55,9,55,25,57,15,481,15,9,529,9,33
%N A298756 Least strong pseudoprime to base n.
%C A298756 a(n)=9 if and only if n == 1 or 8 (mod 9). - _Robert Israel_, Mar 27 2018
%H A298756 Robert Israel, <a href="/A298756/b298756.txt">Table of n, a(n) for n = 2..10000</a>
%H A298756 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/StrongPseudoprime.html">Strong Pseudoprime</a>
%H A298756 <a href="/index/Ps#pseudoprimes">Index entries for sequences related to pseudoprimes</a>
%p A298756 filter:= proc(n,b) local d,s,r;
%p A298756   if isprime(n) then return false fi;
%p A298756   s:= padic:-ordp(n-1,2);
%p A298756   d:= (n-1)/2^s;
%p A298756   if b &^ d mod n = 1 then return true fi;
%p A298756   for r from 0 to s-1 do
%p A298756     if b &^ (d*2^r) + 1 mod n = 0 then return true fi
%p A298756   od;
%p A298756 false
%p A298756 end proc:
%p A298756 f:= proc(b) local n;
%p A298756   for n from 9 by 2 do if filter(n,b) then return n fi od
%p A298756 end proc:
%p A298756 map(f, [$2..100]); # _Robert Israel_, Mar 27 2018
%t A298756 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 A298756 (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 A298756 a(n) = forcomposite(c=1, , if(is_a001262(c, n), return(c))) \\ _Felix Fröhlich_, Mar 28 2018
%Y A298756 Cf. A001262, A020229, A020230, A020231, A020232, A020233, A020234, A020235.
%K A298756 nonn
%O A298756 2,1
%A A298756 _Amiram Eldar_, Jan 26 2018