A056915 -id:A056915 - cp's OEIS frontend

A208846 a(n) = A056915(n) mod 76057 mod 13.

2, 7, 11, 10, 5, 9, 6, 3, 4, 0, 1, 12, 8, 8, 6, 10, 9, 6, 7, 10, 3, 6, 2, 9, 8, 1, 2, 2, 2, 8, 0, 5, 5, 2, 7, 11, 5, 2, 11, 0, 10, 8, 2, 7, 4, 10, 2, 0, 5, 12, 8, 11, 6, 7, 7, 11, 0, 5, 1, 12, 6, 4, 6, 7, 8, 1, 12, 0, 7, 2, 9

Offset: 1

Washington Bomfim, Mar 02 2012

nonn

A056915(n) mod 76057 mod 13 is a bijection from the set of the first 13 terms of A056915 to {0,1,2,3,4,5,6,7,8,9,10,11,12}.
One of the tests for primality described in the first reference when tests x and x is prime, searches a table T composed by the first 13 entries of A056915 to see if x is a strong pseudoprime to bases 2,3 and 5. A fast way to do that is to compute i = x  mod 76057 mod 13, and compare x with T[i]. If x is not equal to T[i], x is prime.
Terms computed using table by Charles R Greathouse IV. See A056915.

Washington Bomfim, A method to find bijections from a set of n integers to {0,1, ... ,n-1}
C. Pomerance, J. L. Selfridge, and S. S. Wagstaff, Jr., The pseudoprimes to 25*10^9, Mathematics of Computation, 35, 1980, pp. 1003-1026.

Cf. A055775.

A208847 A056915(n) mod 5228905 mod 17.

Original entry on oeis.org

3, 4, 13, 15, 8, 14, 9, 5, 0, 11, 16, 10, 2, 12, 7, 1, 6, 16, 3, 10, 5, 8, 7, 16, 6, 11, 13, 6, 10, 6, 11, 16, 9, 1, 1, 15, 5, 1, 14, 7, 15, 2, 14, 9, 2, 6, 14, 3, 3, 14, 12, 6, 2, 4, 10, 16, 6, 10, 9, 3, 3, 1, 7, 9, 11, 5

Offset: 1

Washington Bomfim, Mar 02 2012

nonn

A056915(n) mod 5228905 mod 17 is a bijection from the set of the first 17 terms of A056915 to {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16}.
From an algorithm based on strong pseudoprimes to bases 2,3 and 5, and a table T with the first 17 terms of A056915, we can test if n is prime, odd n, 1 < n < 42550716781. When n is a prime, we check if n belongs to T. A fast way to do that is to compute i = n mod 5228905 mod 17 and compare n with T[i]. If n is not equal to T[i], n is prime.
Terms computed using table by Charles R Greathouse IV. See A056915.

Washington Bomfim, A method to find bijections from a set of n integers to {0,1, ... ,n-1}

Cf. A056915, A055775, A208846.

A001262 Strong pseudoprimes to base 2.

Original entry on oeis.org

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

A020231 Strong pseudoprimes to base 5.

Original entry on oeis.org

781, 1541, 5461, 5611, 7813, 13021, 14981, 15751, 24211, 25351, 29539, 38081, 40501, 44801, 53971, 79381, 100651, 102311, 104721, 112141, 121463, 133141, 141361, 146611, 195313, 211951, 216457, 222301, 251521, 289081, 290629, 298271, 315121

Offset: 1

David W. Wilson

nonn

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

Cf. A005936, A001262 (base-2 SPP), A020229 (base-3 SPP), A215568 (SPP to bases 2 & 5), A215566 (SPP to bases 3 & 5), A056915 (SPP to bases 2, 3 & 5), A074773 (SPP to bases 2, 3, 5 & 7).

nmax = 400000; 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}]]); A020231 = {}; n = 1; While[n < nmax, n = n+2; If[sppQ[n, 5] == True, Print[n]; AppendTo[A020231, n]]]; A020231 (* Jean-François Alcover, Oct 20 2011, after R. J. Mathar *)

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

cp's OEIS Frontend

A208846 a(n) = A056915(n) mod 76057 mod 13.

Views

Author

Keywords

Comments

Links

Crossrefs

A208847 A056915(n) mod 5228905 mod 17.

Views

Author

Keywords

Comments

Links

Crossrefs

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

A020231 Strong pseudoprimes to base 5.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

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

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Extensions