A072276 -id:A072276 - 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

A020229 Strong pseudoprimes to base 3.

Original entry on oeis.org

121, 703, 1891, 3281, 8401, 8911, 10585, 12403, 16531, 18721, 19345, 23521, 31621, 44287, 47197, 55969, 63139, 74593, 79003, 82513, 87913, 88573, 97567, 105163, 111361, 112141, 148417, 152551, 182527, 188191, 211411, 218791, 221761, 226801

Offset: 1

David W. Wilson

nonn

Charles R Greathouse IV, Table of n, a(n) for n = 1..24767 (first 752 terms from R. J. Mathar)
Joerg Arndt, Matters Computational (The Fxtbook), section 39.10, pp. 786-792
Eric Weisstein's World of Mathematics, Strong Pseudoprime
Index entries for sequences related to pseudoprimes

Cf. A001262, A072276, A056915, A074773, A005935.

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

is_A020229(n,b=3)={ bittest(n,0) || return;ispseudoprime(n) && return;my(d=(n-1)>>valuation(n-1,2));Mod(b,n)^d==1 || until(n-1<=d*=2,Mod(b,n)^d+1 || return(1))} \\ M. F. Hasler, Jul 19 2012

A056915 Strong pseudoprimes to bases 2, 3 and 5, i.e., intersection of A001262, A020229, and A020231.

Original entry on oeis.org

25326001, 161304001, 960946321, 1157839381, 3215031751, 3697278427, 5764643587, 6770862367, 14386156093, 15579919981, 18459366157, 19887974881, 21276028621, 27716349961, 29118033181, 37131467521, 41752650241, 42550716781, 43536545821

Offset: 1

Rick L. Shepherd, Feb 12 2002

These first 13 numbers are the only ones less than 25*10^9 which are simultaneously strong pseudoprimes to bases 2, 3 and 5. Taken from the same table - which indicates (only) whether they are also strong pseudoprime (spsp) or pseudoprime (psp) to base 7, 11 and/or 13: 161304001 is spsp to 11; 3215031751 is spsp to base 7 and is psp to both bases 11 and 13; 5764643587 is spsp to base 13; 14386156093 is psp to bases 7, 11 and 13. 15579919981 is psp to base 7 and spsp to base 11; 19887974881 is psp to base 7; and 21276028621 is psp to bases 11 and 13.

P. Ribenboim, The Little Book of Big Primes. Springer-Verlag, NY, 1991, pp. 82-83.

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
Pomerance, C., Selfridge, J.L. and Wagstaff, Jr., S.S. The pseudoprimes to 25*10^9, Mathematics of Computation 35, 1980, pp. 1003-1026.
Eric Weisstein's World of Mathematics, Strong Pseudoprime
Index entries for sequences related to pseudoprimes

Cf. A072276, A001262, A020229, A020231, superset of A074773.

B-file and more terms from Charles R Greathouse IV, Aug 14 2010

A215568 Strong pseudoprimes to base 2 and 5.

Original entry on oeis.org

1907851, 4181921, 4469471, 5256091, 9006401, 9863461, 14709241, 25326001, 40987201, 55729957, 58449847, 67194401, 94502701, 100618933, 109437751, 114305441, 133800661, 135969401, 147028001, 153928133, 161304001, 192857761, 196049701, 213035761, 226359547, 245950561

Offset: 1

M. F. Hasler, Aug 16 2012

nonn

Amiram Eldar, Table of n, a(n) for n = 1..880 (terms below 10^12; terms 1..381 from M. F. Hasler)

Intersection of A001262 and A020231.

Cf. A072276, A215566.

A215566 Strong pseudoprimes to bases 3 and 5.

Original entry on oeis.org

112141, 432821, 1024651, 1563151, 1627921, 3543121, 4291801, 5481451, 8595361, 9780409, 10679131, 11407441, 18790021, 21397381, 22369621, 25326001, 27012001, 32817151, 33796531, 35798491, 42149971, 48064021, 67680491, 99809051, 116151661, 118846151, 129762001

Offset: 1

M. F. Hasler, Aug 16 2012

nonn

Terms A215566[1,...,35] calculated from A020231[1,...,715] and double-checked (up to a(32)=178482151) using A020229[1,...,752].

Amiram Eldar, Table of n, a(n) for n = 1..1209 (terms below 10^12; terms 1..35 from M. F. Hasler)

Intersection of A020229 and A020231.

Cf. A072276, A215568.

A140658 Overpseudoprimes to bases 2 and 3.

Original entry on oeis.org

5173601, 13694761, 16070429, 27509653, 54029741, 66096253, 102690677, 117987841, 193949641, 206304961, 314184487, 390612221, 393611653, 717653129, 960946321, 1157839381, 1236313501, 1481626513, 1860373241, 1921309633, 2217879901, 2412172153, 2626783921

Offset: 1

Vladimir Shevelev, Jul 10 2008

nonn

From the first 19 strong pseudoprimes to bases 2 and 3 (A072276) only 6 are overpseudoprimes to the same bases.

Daniel Suteu, Table of n, a(n) for n = 1..10000 (terms 1..105 from Amiram Eldar)
Index entries for sequences related to pseudoprimes

Intersection of A141232 and A141350; subsequence of A072276.

Cf. A001262, A020229.

More terms from Amiram Eldar, Jun 24 2019

cp's OEIS Frontend

A001262 Strong pseudoprimes to base 2.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Extensions

A020229 Strong pseudoprimes to base 3.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

A056915 Strong pseudoprimes to bases 2, 3 and 5, i.e., intersection of A001262, A020229, and A020231.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

A215568 Strong pseudoprimes to base 2 and 5.

Views

Author

Keywords

Links

Crossrefs

A215566 Strong pseudoprimes to bases 3 and 5.

Views

Author

Keywords

Comments

Links

Crossrefs

A140658 Overpseudoprimes to bases 2 and 3.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions