login
a(f(A074773(n))) = A074773(n); 1 <= n <= 9999; f: N -> {1..9999}.
3

%I #30 Dec 21 2015 12:19:14

%S 457453568161,1362242655901,2152302898747,2273312197621,4341937413061,

%T 4777422165601,11377272352951,13112583010129,23537786498641,

%U 90022554326251,92045875072861,131175316104661

%N a(f(A074773(n))) = A074773(n); 1 <= n <= 9999; f: N -> {1..9999}.

%C Also a table "a" of the 9999 smallest strong pseudoprimes to bases 2,3,5, and 7, indexed by function f. See the expression of f in the first PARI program. The algorithm below is a fast deterministic primality test for integers x, x <= A074773(10000)-1. Note that A074773(10000)-1 > 5.6*10^18 > 2^62.

%C 1. Run Rabin-Miller test only with base 2. If x not pass return composite.

%C 2. Run Rabin-Miller test only with base 3. If x not pass return composite.

%C 3. Run Rabin-Miller test only with base 5. If x not pass return composite.

%C 4. Run Rabin-Miller test only with base 7. If x not pass return composite.

%C 5. Compute i = f(x); if a(i) = x, return composite; otherwise return prime.

%C ---

%C In first reference, p. 1022, there is a test where a table of strong pseudoprimes is used. Terms computed using data from _Charles R Greathouse IV_. See A074773. Third link references file "C:/temp/A.txt", a string with the first 9999 terms of A074773, each term preceded by its number of digits. Second link references file "C:/temp/V.txt", which makes the table V used by function f. It is also a string of numbers, each one preceded by its number of digits.

%H Washington Bomfim, <a href="/A209833/a209833_1.txt">C:/temp/V.txt</a>

%H Washington Bomfim, <a href="/A209833/a209833_2.txt">C:/temp/A.txt</a>

%H 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 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Rabin-MillerStrongPseudoprimeTest.html">Rabin-Miller Strong Pseudoprime Test</a>

%e a(1) = A074773(6) because f(A074773(6)) = 1. (With M = 16992, A074773(6) % 453359393 % M + 1 = 7185, and A074773(6)%450577199 % M + 1 = 7593. After running the first PARI program, one can type V[7185], and V[7593] to see that y=z = V[7185]= V[7593] = 0. So f(A074773(6)) = 1).

%o (PARI)

%o s=Str(read("C:/temp/V.txt"));x=Vec(s);n=0;M=16992;i=1;V=vector(M);k=0;s="";j=0;y=0;z=0;

%o for(n=1,M,k=i+1;s="";for(j=1,eval(x[i]),s=concat(s,x[k]);k++);V[n]=eval(s);i=k);

%o \\

%o f(x)={y=V[x%453359393%M+1]; z=V[x%450577199%M+1]; return((y<=z)*z + (y>z)*y +1);};

%o \\

%o print("Reading file C:/temp/A.txt. Please wait...");s=Str(read("C:/temp/A.txt")); x=Vec(s);i=1;p=vector(9999);

%o for(n=1,9999,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 print("");a=vector(9999); for(i=1,9999,a[f(p[i])]=p[i]);for(i=1,9999, print(i," ",a[i]))

%Y Cf. A208846.

%K nonn,fini,full

%O 1,1

%A _Washington Bomfim_, Mar 14 2012