OFFSET
1,1
COMMENTS
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.
LINKS
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
EXAMPLE
PROG
(PARI)
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]))
CROSSREFS
KEYWORD
nonn,fini,full
AUTHOR
Washington Bomfim, Mar 14 2012
STATUS
approved