A209833 -id:A209833 - cp's OEIS frontend

A209834 a(A074773(n) mod 1519829 mod 18) = A074773(n), 1 <= n <= 18.

3343433905957, 1871186716981, 307768373641, 546348519181, 1362242655901, 2273312197621, 354864744877, 3474749660383, 2366338900801, 602248359169, 3215031751, 2152302898747, 315962312077, 457453568161, 528929554561, 3477707481751, 118670087467, 3461715915661

Offset: 0

Washington Bomfim, Mar 14 2012

From the first reference, for numbers up to 10^12 only four strong pseudoprimality tests (with bases 2, 13, 23, 1662803) are necessary for proving primality. Since A074773(19) = 4341937413061, up to 4.10^12 we can use the four bases 2, 3, 5, 7 and if a number n passes the tests, we check if n is equal to a(n mod 1519829 mod 18). If not, n is prime. A unique comparison is used so we have a primality test equally efficient for an interval four times larger. See the Bomfim link.

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

			A074773(15) mod 1519829 mod 18 = 0, so a(0) = A074773(15).
A074773(11) mod 1519829 mod 18 = 1, so a(1) = A074773(11).

Washington Bomfim, A method to find bijections from a set of n integers to {0,1, ... ,n-1}
G. Jaeschke, On strong pseudoprimes to several bases, Mathematics of Computation, 61 (1993), 915-926.

Cf. A074773, A209833.

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

Original entry on oeis.org

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

Washington Bomfim, Mar 23 2012

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.

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

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

Cf. A074773, A209833, A209834.

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

cp's OEIS Frontend

A209834 a(A074773(n) mod 1519829 mod 18) = A074773(n), 1 <= n <= 18.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs