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

Author

Washington Bomfim, Mar 14 2012

Keywords

• nonn
• fini
• full

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.

Examples

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

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

Crossrefs

Cf. A208846.

Programs

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