A211112 - OEIS

%I #55 Dec 17 2016 10:19:58

%S 39365185894561,52657210792621,11377272352951,15070413782971,

%T 3343433905957,16603327018981,3461715915661,52384617784801,

%U 3477707481751,18996486073489,55712149574381,118670087467

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

%C 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.

%C We can use the algorithm given below to make a primality test to see if an integer x, x < A074773(64) = 60153869469241, is prime.

%C 1. Run Miller-Rabin test with base 2, if x is not prime return composite.

%C 2. Run Miller-Rabin test with base 3, if x is not prime return composite.

%C 3. Run Miller-Rabin test with base 5, if x is not prime return composite.

%C 4. Run Miller-Rabin test with base 7, if x is not prime return composite.

%C 5. Compute i = f(x); if a(i) = x, return composite otherwise return prime.

%C 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.

%H Washington Bomfim, <a href="/A211112/a211112_1.txt">A.txt</a>

%H C. Pomerance, J. L. Selfridge, and S. S. Wagstaff, Jr., <a href="http://dx.doi.org/10.1090/S0025-5718-1980-0572872-7">The pseudoprimes to 25*10^9</a>, Mathematics of Computation 35 (1980), pp. 1003-1026.

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test">Miller-Rabin primality test</a>

%e Because f(A074773(15)) = 5, a(5) = A074773(15).

%o (PARI)

%o f(x)={ f1=x % 20650997 % 63; f2=x % 13936751 % 63; v1=3521775543809890147;

%o v2 = 1700305497776372630; v3 = 4844350019353692337;

%o h1=(f1<=20)*((v1>>(3*f1))%8)+(f1>=42)*((v3>>(3*(f1-42)))%8)+(f1>20&&f1<42)*((v2>>(3*(f1-21)))%8);

%o h2=(f2<=20)*((v1>>(3*f2))%8)+(f2>=42)*((v3>>(3*(f2-42)))%8)+(f2>20&&f2<42)*((v2>>(3*(f2-21)))%8);

%o y = (h1==h2)*f2 + (h1>h2)*f1+(h2>h1)*f2 + 1; return (y);};

%o \\

%o s=Str(read("C:/temp/A074773.txt" )); x=Vec(s);n=0;k=0;j=0;i=1;p=vector(63); y=0;

%o 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);

%o a=vector(63); for(i=1,63, y =f(p[i]); a[y]=p[i]); for(i=1,63, print(i," ",a[i]));

%Y Cf. A074773, A208847, A210588.

%K nonn,fini,full

%O 1,1

%A _Washington Bomfim_, Apr 11 2012

%E Edited by _M. F. Hasler_, Dec 09 2016 and Dec 17 2016