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.

%I A211112 #55 Dec 17 2016 10:19:58
%S A211112 39365185894561,52657210792621,11377272352951,15070413782971,
%T A211112 3343433905957,16603327018981,3461715915661,52384617784801,
%U A211112 3477707481751,18996486073489,55712149574381,118670087467
%N A211112 a(n) is the smallest pseudoprime q in A074773 such that f(q) = n, where f: N -> {1..63} is given below.
%C A211112 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 A211112 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 A211112 1. Run Miller-Rabin test with base 2, if x is not prime return composite.
%C A211112 2. Run Miller-Rabin test with base 3, if x is not prime return composite.
%C A211112 3. Run Miller-Rabin test with base 5, if x is not prime return composite.
%C A211112 4. Run Miller-Rabin test with base 7, if x is not prime return composite.
%C A211112 5. Compute i = f(x); if a(i) = x, return composite otherwise return prime.
%C A211112 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 A211112 Washington Bomfim, <a href="/A211112/a211112_1.txt">A.txt</a>
%H A211112 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 A211112 Wikipedia, <a href="http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test">Miller-Rabin primality test</a>
%e A211112 Because f(A074773(15)) = 5, a(5) = A074773(15).
%o A211112 (PARI)
%o A211112 f(x)={ f1=x % 20650997 % 63; f2=x % 13936751 % 63; v1=3521775543809890147;
%o A211112 v2 = 1700305497776372630; v3 = 4844350019353692337;
%o A211112 h1=(f1<=20)*((v1>>(3*f1))%8)+(f1>=42)*((v3>>(3*(f1-42)))%8)+(f1>20&&f1<42)*((v2>>(3*(f1-21)))%8);
%o A211112 h2=(f2<=20)*((v1>>(3*f2))%8)+(f2>=42)*((v3>>(3*(f2-42)))%8)+(f2>20&&f2<42)*((v2>>(3*(f2-21)))%8);
%o A211112 y = (h1==h2)*f2 + (h1>h2)*f1+(h2>h1)*f2 + 1; return (y);};
%o A211112 \\
%o A211112 s=Str(read("C:/temp/A074773.txt" )); x=Vec(s);n=0;k=0;j=0;i=1;p=vector(63); y=0;
%o A211112 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 A211112 a=vector(63); for(i=1,63, y =f(p[i]); a[y]=p[i]); for(i=1,63, print(i," ",a[i]));
%Y A211112 Cf. A074773, A208847, A210588.
%K A211112 nonn,fini,full
%O A211112 1,1
%A A211112 _Washington Bomfim_, Apr 11 2012
%E A211112 Edited by _M. F. Hasler_, Dec 09 2016 and Dec 17 2016