A210588 - OEIS

%I #16 Sep 07 2013 13:46:44

%S 6597606223981,3474749660383,5792018372251,307768373641,3477707481751,

%T 1362242655901,3461715915661,4341937413061,5537838510751,

%U 10710604680091,2273312197621,602248359169,10087771603687,3343433905957,2366338900801,8006855187361,457453568161,11377272352951,118670087467,354864744877,2152302898747,528929554561,546348519181,315962312077,3215031751,4777422165601,1871186716981

%N Twenty-seven smaller strong pseudoprimes to bases 2,3,5,7 arranged in order given by a function f:N->{1..27}

%C We can use a table with the terms of this sequence, and the function f:N->{1..27} defined below, in the final of a primality test based on those strong pseudoprimes. Since A074773(28) = 11,458,457,613,541; this test is valid for numbers up to 1.1*10^13. Only one table look-up will be necessary to see if an odd integer x is prime. From the first reference we find appropriate algorithms for large tables.

%C f(x) = (h1=h2)*f1+(h1>h2)*f1+(h2>h1)*f2 + 1, where f1 = x mod 24729742 mod 27, f2 = x mod 24729769 mod 27, h1 = floor(164352/(2^f1)) mod 2, and h2 = floor(164352/(2^f2)) mod 2.

%C Terms computed using table by Charles R Greathouse IV. See A074773.

%H George Havas and Bohdan S. Majewski, <a href="http://itee.uq.edu.au/~havas/TR0234.pdf">Optimal algorithms for minimal perfect hashing</a>

%e A074773(1) appears in the 25th place because f(A074773(1)) = 25.

%o (PARI)

%o f(x)={f1 = x % 24729742 % 27; f2 = x % 24729769 % 27; h1 = 164352 >> f1 % 2;

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

%o p1=[3215031751,118670087467,307768373641,315962312077,354864744877,457453568161];

%o p2=[528929554561,546348519181,602248359169,1362242655901,1871186716981,2152302898747];

%o p3=[2273312197621,2366338900801,3343433905957,3461715915661,3474749660383];

%o p4=[3477707481751,4341937413061,4777422165601,5537838510751,5792018372251];

%o p5=[6597606223981,8006855187361,10087771603687,10710604680091,11377272352951];

%o a=vector(27); for(i=1,6, a[f(p1[i])] = p1[i]); for(i=1,6, a[f(p2[i])] = p2[i]);

%o for(i=1,5, a[f(p3[i])] = p3[i]); for(i=1,5, a[f(p4[i])] = p4[i]);

%o for(i=1,5, a[f(p5[i])] = p5[i]); for(i=1,27, print1(a[i],", "));

%Y Cf. A074773, A209833, A209834.

%K nonn,fini,full

%O 1,1

%A _Washington Bomfim_, Mar 23 2012