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

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.

Links

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

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

Example

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

Prog

(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], ", "));

Crossrefs

Cf. A074773, A209833, A209834.

Sequence in context: A094910 A378474 A295353 * A023051 A345865 A003826

Adjacent sequences: A210585 A210586 A210587 * A210589 A210590 A210591

Keyword

nonn,fini,full

Author

Washington Bomfim, Mar 23 2012

Status

approved