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

6597606223981, 3474749660383, 5792018372251, 307768373641, 3477707481751, 1362242655901, 3461715915661, 4341937413061, 5537838510751, 10710604680091, 2273312197621, 602248359169, 10087771603687, 3343433905957, 2366338900801, 8006855187361, 457453568161, 11377272352951, 118670087467, 354864744877, 2152302898747, 528929554561, 546348519181, 315962312077, 3215031751, 4777422165601, 1871186716981

Offset: 1

Author

Washington Bomfim, Mar 23 2012

Keywords

• nonn
• fini
• full

Comments

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.

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.

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

Examples

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

Links

• George Havas and Bohdan S. Majewski, Optimal algorithms for minimal perfect hashing

Crossrefs

Cf. A074773, A209833, A209834.

Programs

PARI

f(x)={f1 = x % 24729742 % 27; f2 = x % 24729769 % 27; h1 = 164352 >> f1 % 2;
h2=164352 >> f2 % 2; return((h1==h2)*f1 + (h1>h2)*f1+(h2>h1)*f2 + 1); };
p1=[3215031751,118670087467,307768373641,315962312077,354864744877,457453568161];
p2=[528929554561,546348519181,602248359169,1362242655901,1871186716981,2152302898747];
p3=[2273312197621,2366338900801,3343433905957,3461715915661,3474749660383];
p4=[3477707481751,4341937413061,4777422165601,5537838510751,5792018372251];
p5=[6597606223981,8006855187361,10087771603687,10710604680091,11377272352951];
a=vector(27); for(i=1,6, a[f(p1[i])] = p1[i]); for(i=1,6, a[f(p2[i])] = p2[i]);
for(i=1,5, a[f(p3[i])] = p3[i]); for(i=1,5, a[f(p4[i])] = p4[i]);
for(i=1,5, a[f(p5[i])] = p5[i]); for(i=1,27, print1(a[i],", "));