login
A211112
a(n) is the smallest pseudoprime q in A074773 such that f(q) = n, where f: N -> {1..63} is given below.
1
39365185894561, 52657210792621, 11377272352951, 15070413782971, 3343433905957, 16603327018981, 3461715915661, 52384617784801, 3477707481751, 18996486073489, 55712149574381, 118670087467
OFFSET
1,1
COMMENTS
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.
LINKS
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.
EXAMPLE
Because f(A074773(15)) = 5, a(5) = A074773(15).
PROG
(PARI)
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]));
CROSSREFS
KEYWORD
nonn,fini,full
AUTHOR
Washington Bomfim, Apr 11 2012
EXTENSIONS
Edited by M. F. Hasler, Dec 09 2016 and Dec 17 2016
STATUS
approved