A074773 -id:A074773 - cp's OEIS frontend

A209833 a(f(A074773(n))) = A074773(n); 1 <= n <= 9999; f: N -> {1..9999}.

457453568161, 1362242655901, 2152302898747, 2273312197621, 4341937413061, 4777422165601, 11377272352951, 13112583010129, 23537786498641, 90022554326251, 92045875072861, 131175316104661

Offset: 1

Washington Bomfim, Mar 14 2012

Also a table "a" of the 9999 smallest strong pseudoprimes to bases 2,3,5, and 7, indexed by function f. See the expression of f in the first PARI program. The algorithm below is a fast deterministic primality test for integers x, x <= A074773(10000)-1. Note that A074773(10000)-1 > 5.6*10^18 > 2^62.
1. Run Rabin-Miller test only with base 2. If x not pass return composite.
2. Run Rabin-Miller test only with base 3. If x not pass return composite.
3. Run Rabin-Miller test only with base 5. If x not pass return composite.
4. Run Rabin-Miller test only with base 7. If x not pass return composite.
5. Compute i = f(x); if a(i) = x, return composite; otherwise return prime.
---
In first reference, p. 1022, there is a test where a table of strong pseudoprimes is used. Terms computed using data from Charles R Greathouse IV. See A074773. Third link references file "C:/temp/A.txt", a string with the first 9999 terms of A074773, each term preceded by its number of digits. Second link references file "C:/temp/V.txt", which makes the table V used by function f. It is also a string of numbers, each one preceded by its number of digits.

			a(1) = A074773(6) because f(A074773(6)) = 1. (With M = 16992, A074773(6) % 453359393 % M + 1 = 7185, and A074773(6)%450577199 % M + 1 = 7593. After running the first PARI program, one can type V[7185], and V[7593] to see that y=z = V[7185]= V[7593] = 0. So f(A074773(6)) = 1).

Washington Bomfim, C:/temp/V.txt
Washington Bomfim, C:/temp/A.txt
C. Pomerance, J. L. Selfridge, and S. S. Wagstaff, Jr., The pseudoprimes to 25*10^9, Mathematics of Computation 35 (1980), pp. 1003-1026.
Eric Weisstein's World of Mathematics, Rabin-Miller Strong Pseudoprime Test

Cf. A208846.

s=Str(read("C:/temp/V.txt"));x=Vec(s);n=0;M=16992;i=1;V=vector(M);k=0;s="";j=0;y=0;z=0;
for(n=1,M,k=i+1;s="";for(j=1,eval(x[i]),s=concat(s,x[k]);k++);V[n]=eval(s);i=k);
\\
f(x)={y=V[x%453359393%M+1]; z=V[x%450577199%M+1]; return((y<=z)*z + (y>z)*y +1);};
\\
print("Reading file C:/temp/A.txt. Please wait...");s=Str(read("C:/temp/A.txt")); x=Vec(s);i=1;p=vector(9999);
for(n=1,9999,k=i+2;s="";for(j=1,eval(concat(x[i],x[i+1])),s=concat(s,x[k]);k++); p[n]=eval(s);i=k);
print("");a=vector(9999); for(i=1,9999,a[f(p[i])]=p[i]);for(i=1,9999, print(i," ",a[i]))

A209834 a(A074773(n) mod 1519829 mod 18) = A074773(n), 1 <= n <= 18.

Original entry on oeis.org

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

Offset: 0

Washington Bomfim, Mar 14 2012

From the first reference, for numbers up to 10^12 only four strong pseudoprimality tests (with bases 2, 13, 23, 1662803) are necessary for proving primality. Since A074773(19) = 4341937413061, up to 4.10^12 we can use the four bases 2, 3, 5, 7 and if a number n passes the tests, we check if n is equal to a(n mod 1519829 mod 18). If not, n is prime. A unique comparison is used so we have a primality test equally efficient for an interval four times larger. See the Bomfim link.

Terms computed using table by Charles R Greathouse IV. See A074773.

			A074773(15) mod 1519829 mod 18 = 0, so a(0) = A074773(15).
A074773(11) mod 1519829 mod 18 = 1, so a(1) = A074773(11).

Washington Bomfim, A method to find bijections from a set of n integers to {0,1, ... ,n-1}
G. Jaeschke, On strong pseudoprimes to several bases, Mathematics of Computation, 61 (1993), 915-926.

Cf. A074773, A209833.

A211112 a(n) is the smallest pseudoprime q in A074773 such that f(q) = n, where f: N -> {1..63} is given below.

Original entry on oeis.org

39365185894561, 52657210792621, 11377272352951, 15070413782971, 3343433905957, 16603327018981, 3461715915661, 52384617784801, 3477707481751, 18996486073489, 55712149574381, 118670087467

Offset: 1

Washington Bomfim, Apr 11 2012

Also, list of the 63 smallest strong pseudoprimes to bases 2,3,5, and 7, indexed by function f. See the expression of f in the first PARI program.
We can use the algorithm given below to make a primality test to see if an integer x, x < A074773(64) = 60153869469241, is prime.
1. Run Miller-Rabin test with base 2, if x is not prime return composite.
2. Run Miller-Rabin test with base 3, if x is not prime return composite.
3. Run Miller-Rabin test with base 5, if x is not prime return composite.
4. Run Miller-Rabin test with base 7, if x is not prime return composite.
5. Compute i = f(x); if a(i) = x, return composite otherwise return prime.
In first reference, pp 1022, there is a test where a table of strong pseudoprimes is used. Terms computed using data from Charles R Greathouse IV. See A074773. Second link references the file "C:/temp/A074773.txt" used by the first PARI program. This file is a string with the first 63 terms of A074773, each term preceded by its number of digits.

			Because f(A074773(15)) = 5, a(5) = A074773(15).

Washington Bomfim, A.txt
C. Pomerance, J. L. Selfridge, and S. S. Wagstaff, Jr., The pseudoprimes to 25*10^9, Mathematics of Computation 35 (1980), pp. 1003-1026.
Wikipedia, Miller-Rabin primality test

Cf. A074773, A208847, A210588.

f(x)={ f1=x % 20650997 % 63; f2=x % 13936751 % 63; v1=3521775543809890147;
v2 = 1700305497776372630; v3 = 4844350019353692337;
h1=(f1<=20)*((v1>>(3*f1))%8)+(f1>=42)*((v3>>(3*(f1-42)))%8)+(f1>20&&f1<42)*((v2>>(3*(f1-21)))%8);
h2=(f2<=20)*((v1>>(3*f2))%8)+(f2>=42)*((v3>>(3*(f2-42)))%8)+(f2>20&&f2<42)*((v2>>(3*(f2-21)))%8);
y = (h1==h2)*f2 + (h1>h2)*f1+(h2>h1)*f2 + 1; return (y);};
\\
s=Str(read("C:/temp/A074773.txt" )); x=Vec(s);n=0;k=0;j=0;i=1;p=vector(63); y=0;
for(n=1,63,k=i+2;s="";for(j=1,eval(concat(x[i],x[i+1])),s=concat(s,x[k]);k++); p[n]=eval(s);i=k);
a=vector(63); for(i=1,63, y =f(p[i]); a[y]=p[i]); for(i=1,63, print(i," ",a[i]));

Edited by M. F. Hasler, Dec 09 2016 and Dec 17 2016

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

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

A188755 Strong pseudoprimes to bases 11, 13 and 17.

Original entry on oeis.org

10267951, 38248981, 39547171, 54637831, 123771511, 264350521, 284166877, 317712877, 585281791, 842220289, 1480849831, 2144961253, 2385076987, 3256366051, 3363763231, 3383477191, 3637831753, 4042578403, 5541525331

Offset: 1

R. J. Mathar, Apr 09 2011, Mar 08 2012

nonn

Intersection of A020237, A020239 and A020243.

Index entries for sequences related to pseudoprimes

Cf. A074773.

A210588 Twenty-seven smaller strong pseudoprimes to bases 2,3,5,7 arranged in order given by a function f:N->{1..27}.

Original entry on oeis.org

6597606223981, 3474749660383, 5792018372251, 307768373641, 3477707481751, 1362242655901, 3461715915661, 4341937413061, 5537838510751, 10710604680091, 2273312197621, 602248359169, 10087771603687, 3343433905957, 2366338900801, 8006855187361, 457453568161, 11377272352951, 118670087467, 354864744877, 2152302898747, 528929554561, 546348519181, 315962312077, 3215031751, 4777422165601, 1871186716981

Offset: 1

Washington Bomfim, Mar 23 2012

We can use a table with the terms of this sequence, and the function f:N->{1..27} defined below, in the final of a primality test based on those strong pseudoprimes. Since A074773(28) = 11,458,457,613,541; this test is valid for numbers up to 1.1*10^13. Only one table look-up will be necessary to see if an odd integer x is prime. From the first reference we find appropriate algorithms for large tables.
f(x) = (h1=h2)*f1+(h1>h2)*f1+(h2>h1)*f2 + 1, where f1 = x mod 24729742 mod 27, f2 = x mod 24729769 mod 27, h1 = floor(164352/(2^f1)) mod 2, and h2 = floor(164352/(2^f2)) mod 2.
Terms computed using table by Charles R Greathouse IV. See A074773.

			A074773(1) appears in the 25th place because f(A074773(1)) = 25.

George Havas and Bohdan S. Majewski, Optimal algorithms for minimal perfect hashing

Cf. A074773, A209833, A209834.

f(x)={f1 = x % 24729742 % 27; f2 = x % 24729769 % 27; h1 = 164352 >> f1 % 2;
h2=164352 >> f2 % 2; return((h1==h2)*f1 + (h1>h2)*f1+(h2>h1)*f2 + 1); };
p1=[3215031751,118670087467,307768373641,315962312077,354864744877,457453568161];
p2=[528929554561,546348519181,602248359169,1362242655901,1871186716981,2152302898747];
p3=[2273312197621,2366338900801,3343433905957,3461715915661,3474749660383];
p4=[3477707481751,4341937413061,4777422165601,5537838510751,5792018372251];
p5=[6597606223981,8006855187361,10087771603687,10710604680091,11377272352951];
a=vector(27); for(i=1,6, a[f(p1[i])] = p1[i]); for(i=1,6, a[f(p2[i])] = p2[i]);
for(i=1,5, a[f(p3[i])] = p3[i]); for(i=1,5, a[f(p4[i])] = p4[i]);
for(i=1,5, a[f(p5[i])] = p5[i]); for(i=1,27, print1(a[i],", "));

A209395 Strong pseudoprimes to bases 19, 23 and 29.

Original entry on oeis.org

4224533, 5903497, 16462297, 22028203, 44068001, 336273211, 1067437801, 1813073653, 1876485691, 1894909141, 2072488771, 2458231903, 2791053541, 2827961221, 3733646491, 4333572253

Offset: 1

R. J. Mathar, Mar 07 2012

nonn

Intersection of A020245, A020249 and A020255.

Cf. A074773, A188755.

PARI
```
/* see A001262, A020237, A020239 */
```

cp's OEIS Frontend

A209833 a(f(A074773(n))) = A074773(n); 1 <= n <= 9999; f: N -> {1..9999}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A209834 a(A074773(n) mod 1519829 mod 18) = A074773(n), 1 <= n <= 18.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A211112 a(n) is the smallest pseudoprime q in A074773 such that f(q) = n, where f: N -> {1..63} is given below.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Extensions

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

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

A188755 Strong pseudoprimes to bases 11, 13 and 17.

Views

Author

Keywords

Comments

Links

Crossrefs

A210588 Twenty-seven smaller strong pseudoprimes to bases 2,3,5,7 arranged in order given by a function f:N->{1..27}.

Views