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,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

Table of n, a(n) for n=1..12.

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

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

Cf. A074773, A208847, A210588.

Sequence in context: A122126 A318575 A337915 * A132389 A186913 A262193

Adjacent sequences: A211109 A211110 A211111 * A211113 A211114 A211115

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