A020233 -id:A020233 - cp's OEIS frontend

A001262 Strong pseudoprimes to base 2.

2047, 3277, 4033, 4681, 8321, 15841, 29341, 42799, 49141, 52633, 65281, 74665, 80581, 85489, 88357, 90751, 104653, 130561, 196093, 220729, 233017, 252601, 253241, 256999, 271951, 280601, 314821, 357761, 390937, 458989, 476971, 486737

Offset: 1

N. J. A. Sloane

The number 2^k-1 is in the sequence iff k is in A054723 or in A001567. - Thomas Ordowski, Sep 02 2016

The number (2^k+1)/3 is in the sequence iff k is in A127956. - Davide Rotondo, Aug 13 2021

			From _Michael B. Porter_, Sep 04 2016: (Start)
For k = 577, k-1 = 576 = 9*2^6. Since 2^(9*2^3) = 2^72 == -1 (mod 577), 577 passes the primality test, but since it is actually prime, it is not in the sequence.
For k = 3277, k-1 = 3276 = 819*2^2, and 2^(819*2) == -1 (mod 3277), so k passes the primality test, and k = 3277 = 29*113 is composite, so 3277 is in the sequence. (End)

R. K. Guy, Unsolved Problems Theory Numbers, A12.
P. Ribenboim, The Book of Prime Number Records. Springer-Verlag, NY, 2nd ed., 1989, p. 95.

T. D. Noe, Table of n, a(n) for n = 1..10000 (using data from A001567)
Joerg Arndt, Matters Computational (The Fxtbook), section 39.10, pp. 786-792.
Chris Caldwell, Strong probable prime.
Eric Weisstein's World of Mathematics, Strong Pseudoprime.
OEIS Wiki, Strong Pseudoprime.
Wikipedia, Strong pseudoprime.
Index entries for sequences related to pseudoprimes

Cf. A001567 (pseudoprimes to base 2), A020229 (strong pseudoprimes to base 3), A020231 (base 5), A020233 (base 7).

Cf. A072276 (SPP to base 2 and 3), A215568 (SPP to base 2 and 5), A056915 (SPP to base 2,3 and 5), A074773 (SPP to base 2,3,5 and 7).

A007814 := proc(n) padic[ordp](n,2) ; end proc:
isStrongPsp := proc(n,b) local d,s,r; if type(n,'even') or n<=1 then return false; elif isprime(n) then return false; else s := A007814(n-1) ; d := (n-1)/2^s ; if modp(b &^ d,n) = 1 then return true; else for r from 0 to s-1 do if modp(b &^ d,n) = n-1 then return true; end if; d := 2*d ; end do: return false; end if; end if; end proc:
isA001262 := proc(n) isStrongPsp(n,2) ; end proc:
for n from 1 by 2 do if isA001262(n) then print(n); end if; end do:
# R. J. Mathar, Apr 05 2011

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, n] == n-1, Return[True]]; d = 2*d, {s}]]); lst = {}; k = 3; While[k < 500000, If[sppQ[k, 2], Print[k]; AppendTo[lst, k]]; k += 2]; lst (* Jean-François Alcover, Oct 20 2011, after R. J. Mathar *)

isStrongPsp(n,b)={
        my(s,d,r,bm) ;
        if( (n% 2) ==0 || n <=1, return(0) ;) ;
        if(isprime(n), return(0) ;) ;
        s = valuation(n-1,2) ;
        d = (n-1)/2^s ;
        bm = Mod(b,n)^d ;
        if ( bm == Mod(1,n), return(1) ;) ;
        for(r=0,s-1,
                bm = Mod(b,n)^d ;
                if ( bm == Mod(-1,n),
                        return(1) ;
                ) ;
                d *= 2;
        ) ;
        return(0);
}
isA001262(n)={
        isStrongPsp(n,2)
}
{
for(n=1,10000000000,
    if(isA001262(n),
        print(n)
    ) ;
) ;
} \\ R. J. Mathar, Mar 07 2012

is_A001262(n,a=2)={ (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} \\ M. F. Hasler, Aug 16 2012

More terms from David W. Wilson, Aug 15 1996

A074773 Strong pseudoprimes to bases 2, 3, 5 and 7.

Original entry on oeis.org

3215031751, 118670087467, 307768373641, 315962312077, 354864744877, 457453568161, 528929554561, 546348519181, 602248359169, 1362242655901, 1871186716981, 2152302898747, 2273312197621, 2366338900801, 3343433905957, 3461715915661, 3474749660383, 3477707481751, 4341937413061, 4777422165601, 5537838510751

Offset: 1

Don Reble, Sep 07 2002

nonn

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
Washington Bomfim, Table with all 16757 terms up to 2^64
G. Jaeschke, On strong pseudoprimes to several bases, Mathematics of Computation, 61 (1993), 915-926.
Eric Weisstein's World of Mathematics, Miller's Primality Test
Index entries for sequences related to pseudoprimes

Cf. A001262, A020229, A020231, A020233, A056915.

sprp(n,b)=my(s=valuation(n-1,2),d=Mod(b,n)^(n>>s)); if(d==1, return(1)); for(i=1,s-1, if(d==-1, return(1)); d=d^2;); d==-1
is(n)=sprp(n,2) && sprp(n,3) && sprp(n,5) && sprp(n,7) && !isprime(n) \\ Charles R Greathouse IV, Sep 14 2015

b-file, link, and editing from Charles R Greathouse IV, Aug 14 2010

A020230 Strong pseudoprimes to base 4.

Original entry on oeis.org

341, 1387, 2047, 3277, 4033, 4371, 4681, 5461, 8321, 8911, 10261, 13747, 14491, 15709, 15841, 19951, 29341, 31621, 42799, 49141, 49981, 52633, 60787, 65077, 65281, 74665, 80581, 83333, 85489, 88357, 90751, 104653, 123251, 129921, 130561, 137149

Offset: 1

David W. Wilson

nonn

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..229 from R. J. Mathar)
Eric Weisstein's World of Mathematics, Strong Pseudoprime
Index entries for sequences related to pseudoprimes

Cf. A020136 (base 4), A001262 (base 2), A020229 (base 3), A020231 (base 5), A020232 (base 6), A020233 (base 7), A020234 (base 8), A020235 (base 9), A020236 (base 10), A020237 (base 11), A020238 (base 12).

A020234 Strong pseudoprimes to base 8.

Original entry on oeis.org

9, 65, 481, 511, 1417, 2047, 2501, 3277, 3641, 4033, 4097, 4681, 8321, 11041, 15841, 16589, 19561, 24311, 24929, 29341, 41441, 42799, 45761, 49141, 52429, 52633, 54161, 55969, 56033, 59291, 61337, 65281, 66197, 74023, 74665, 77161, 80581, 85489, 87061

Offset: 1

David W. Wilson

nonn

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..237 from R. J. Mathar)
Eric Weisstein's World of Mathematics, Strong Pseudoprime
Index entries for sequences related to pseudoprimes

Cf. A020137, A001262, A020229, A020230, A020231, A020232, A020233.

A071294 Number of witnesses for strong pseudoprimality of 2n+1, i.e., number of bases b, 1 <= b <= 2n, in which 2n+1 is a strong pseudoprime.

Original entry on oeis.org

2, 4, 6, 2, 10, 12, 2, 16, 18, 2, 22, 4, 2, 28, 30, 2, 2, 36, 2, 40, 42, 2, 46, 6, 2, 52, 2, 2, 58, 60, 2, 6, 66, 2, 70, 72, 2, 2, 78, 2, 82, 6, 2, 88, 18, 2, 2, 96, 2, 100, 102, 2, 106, 108, 2, 112, 2, 2, 2, 10, 2, 4, 126, 2, 130, 18, 2, 136, 138, 2, 2, 6, 2, 148, 150, 2, 2, 156, 2, 2

Offset: 1

J.-F. Guiffes (guiffes.jean-francois(AT)wanadoo.fr), Jun 11 2002

nonn

Number of integers b, 1 <= b <= 2n, such that if 2n = 2^k*m with odd m, then the sequence (b^m, b^(2*m), ..., b^(2^k*m)) modulo 2n+1 satisfies the Rabin-Miller test.
Comments from R. J. Mathar, Jul 03 2012 (Start)
The subsequence related to composite 2n+1 is characterized with records in A195328 and associated 2n+1 tabulated in A141768.
Let N = 2n+1 = product_{i=1..s} p_i^r_i be the prime factorization of the odd 2n+1. Related odd parts q and q_i are defined by N-1=2^k*q and p_i-1 = 2^(k_i)*q_i, with sorting such that k_1 <= k_2 <=k_3... Then a(n) = (1+sum_{j=0..k1-1} 2^(j*s)) *product_{i=1..s} gcd(q,qi).
Reduces to A006093 if 2n+1 is prime.
This might be correlated with 2*A195508(n). (End)

Paulo Ribenboim, The Little Book of Bigger Primes, 2nd ed., Springer-Verlag, New York, 2004, p. 98.

Amiram Eldar, Table of n, a(n) for n = 1..10000
F. Arnault, The Rabin-Monier theorem for Lucas pseudoprimes, Mathematics of Computation, vol. 66, no 218, April 1997, pp. 869-881.
Louis Monier, Evaluation and comparison of two efficient primality testing algorithms, Theoretical Computer Science, Vol. 11 (1980), pp. 97-108.
Wikipedia, Strong pseudoprime
Index entries for sequences related to pseudoprimes

Cf. A000265, A001221, A006093, A007814, A063994, A141768, A195328.
Cf. also A001262, A020229, A020231, A020233.
Different from A060684.

rabinmiller := proc(n,a); k := 0; mu := n-1; while irem(mu,2)=0 do k := k+1; mu := mu/2 od; G := a&^mu mod(n); h := 0; if G=1 then RETURN(1) else while h1 do h := h+1; G := G&^2 mod n; od; if h n-1 then RETURN(0) else RETURN(1) fi; if G=1 then RETURN(1); fi; fi; end; compte := proc(n) local l; RETURN(sum('rabinmiller(2*n+1,l)','l'=1..2*n)); end;
Maple code from R. J. Mathar, Jul 03 2012 (Start)
A000265 := proc(n)
     n/2^padic[ordp](n,2) ;
end proc:
a := proc(n)
     q := A000265(n-1) ;
     B := 1;
     s := 0 ;
     k1 := 10000000000000 ;
     for pf in ifactors(n)[2] do
         pi := op(1,pf) ;
         qi := A000265(pi-1) ;
         ki := ilog2((pi-1)/qi) ;
         k1 := min(k1,ki) ;
         B := B*igcd(q,qi) ;
         s := s+1 ;
     end do:
     1+add(2^(j*s),j=0..k1-1) ;
     return B*% ;
end proc:
seq(a(2*n+1),n=1..60) ;

o[n_] := (n-1)/2^IntegerExponent[n-1, 2]; a[n_?PrimeQ] := n-1; a[n_] := Module[{p = FactorInteger[n][[;;, 1]]}, om = Length[p]; Product[GCD[o[n], o[p[[k]]]], {k, 1, om}] * (1 + (2^(om * Min[IntegerExponent[#, 2]& /@ (p - 1)]) - 1)/(2^om - 1))]; Table[a[n], {n, 3, 121, 2}] (* Amiram Eldar, Nov 08 2019 *)

For k = 2*n+1, a(k) = k - 1 if k is prime, otherwise, a(k) = (1 + 2^(omega(k)*nu(k)) - 1)/(2^omega(k)-1)) * Product_{p|k} gcd(od(k-1), od(p-1)), where omega(m) is the number of distinct prime factors of m (A001221), od(m) is the largest odd divisor of m (A000265) and nu(m) = min_{p|m} A007814(p-1). - Amiram Eldar, Nov 08 2019

Edited by Max Alekseyev, Sep 20 2018

Edited by N. J. A. Sloane, Nov 15 2019, merging R. J. Mathar's A182291 with this entry.

A298756 Least strong pseudoprime to base n.

Original entry on oeis.org

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

Amiram Eldar, Jan 26 2018

nonn

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

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

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

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

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

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

A020237 Strong pseudoprimes to base 11.

Original entry on oeis.org

133, 793, 2047, 4577, 5041, 12403, 13333, 14521, 17711, 23377, 43213, 43739, 47611, 48283, 49601, 50737, 50997, 56057, 58969, 68137, 74089, 85879, 86347, 87913, 88831, 102173, 111055, 114211, 115231, 137149, 139231, 171601, 172369, 193249, 196555

Offset: 1

David W. Wilson

nonn

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..636 from R. J. Mathar)
Index entries for sequences related to pseudoprimes

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

/* insert A001262 code here */
isA020237(n)={
        isStrongPsp(n,11)
}
{
for(n=1,10000000000,
        if(isA020237(n), print(n) ;) ;
) ;
} /* R. J. Mathar, Mar 07 2012 */

A020236 Strong pseudoprimes to base 10.

Original entry on oeis.org

9, 91, 1729, 4187, 6533, 8149, 8401, 10001, 11111, 19201, 21931, 50851, 79003, 83119, 94139, 100001, 102173, 118301, 118957, 134863, 139231, 148417, 158497, 166499, 188191, 196651, 201917, 216001, 226273, 231337, 237169, 251251, 287809, 302177

Offset: 1

David W. Wilson

nonn

			From _Alonso del Arte_, Aug 10 2018: (Start)
9 is a strong pseudoprime to base 10. It's not enough to check that 10^8 = 1 mod 9. Since 8 = 1 * 2^3, we also need to verify that 10 = 1 mod 9 and 10^2 = 1 mod 9 as well. Since these are both equal to 1, we see that 9 is indeed a strong pseudoprime to base 10.
91 is also a strong pseudoprime to base 10. Besides checking that 10^90 = 1 mod 91, since 90 = 45 * 2, we also check that 10^45 = -1 mod 91; the -1 is enough to satisfy the definition of a strong pseudoprime.
99 is a Fermat pseudoprime to base 10 (see A005939) but it is not a strong pseudoprime to base 10. Although 10^98 = 1 mod 99, since 98 = 49 * 2, we have to check 10^49 mod 99, and there we find not -1 nor 1 but 10. Therefore 99 is not in this sequence. (End)

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..203 from R. J. Mathar)
Index entries for sequences related to pseudoprimes

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

strongPseudoprimeQ[b_, n_] := Module[{rems = Table[PowerMod[b, (n - 1)/2^expo, n], {expo, 0, IntegerExponent[n - 1,2]}]}, (rems[[-1]] == 1 || MemberQ[rems, n - 1]) && PowerMod[b, n - 1, n] == 1]; max = 5000; Select[Complement[Range[2, max], Prime[Range[PrimePi[max]]]], strongPseudoprimeQ[10, #] &] (* Alonso del Arte, Aug 10 2018 *)

A020238 Strong pseudoprimes to base 12.

Original entry on oeis.org

91, 133, 145, 247, 1649, 1729, 2821, 8911, 9073, 10585, 13051, 13333, 16471, 19517, 20737, 21361, 24013, 24727, 26467, 29539, 31483, 31621, 34219, 34861, 35881, 38311, 38503, 40321, 53083, 67861, 79381, 79501, 88831, 97351, 115231, 121301, 131977

Offset: 1

David W. Wilson

nonn

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..210 from R. J. Mathar)
Index entries for sequences related to pseudoprimes

Cf. A020140, A001262 (base 2), A020229 (base 3), A020230, A020231, A020232, A020233, A020234, A020235, A020236, A020237.

A020240 Strong pseudoprimes to base 14.

Original entry on oeis.org

15, 841, 2743, 3277, 5713, 6541, 7171, 9073, 18721, 21667, 22261, 23521, 38221, 38417, 40501, 41371, 49471, 58255, 68401, 71969, 79003, 88381, 91681, 95033, 96049, 97469, 110309, 115417, 119341, 124609, 134413, 141373, 165677, 211951, 226801

Offset: 1

David W. Wilson

nonn

R. J. Mathar, Table of n, a(n) for n = 1..218
Index entries for sequences related to pseudoprimes

Cf. A001262 (base 2), A020233 (base 7)

cp's OEIS Frontend

A001262 Strong pseudoprimes to base 2.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Extensions

A074773 Strong pseudoprimes to bases 2, 3, 5 and 7.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Extensions

A020230 Strong pseudoprimes to base 4.

Views

Author

Keywords

Links

Crossrefs

A020234 Strong pseudoprimes to base 8.

Views

Author

Keywords

Links

Crossrefs

A071294 Number of witnesses for strong pseudoprimality of 2n+1, i.e., number of bases b, 1 <= b <= 2n, in which 2n+1 is a strong pseudoprime.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A298756 Least strong pseudoprime to base n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A020237 Strong pseudoprimes to base 11.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

A020236 Strong pseudoprimes to base 10.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

A020238 Strong pseudoprimes to base 12.

Views