A210588 -id:A210588 - cp's OEIS frontend

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

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

cp's OEIS Frontend

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