|
| |
|
|
A209833
|
|
a(f(A074773(n))) = A074773(n); 1 <= n <= 9999; f: N -> {1..9999}.
|
|
3
|
|
|
|
457453568161, 1362242655901, 2152302898747, 2273312197621, 4341937413061, 4777422165601, 11377272352951, 13112583010129, 23537786498641, 90022554326251, 92045875072861, 131175316104661
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
C. Pomerance, J. L. Selfridge, and S. S. Wagstaff, Jr., The pseudoprimes to 25*10^9, Mathematics of Computation 35 (1980), pp. 1003-1026.
|
|
|
EXAMPLE
|
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).
|
|
|
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
|
|
|
|
STATUS
|
approved
|
| |
|
|
