cp's OEIS Frontend

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

%I A209833 #31 Feb 16 2025 08:33:16
%S A209833 457453568161,1362242655901,2152302898747,2273312197621,4341937413061,
%T A209833 4777422165601,11377272352951,13112583010129,23537786498641,
%U A209833 90022554326251,92045875072861,131175316104661
%N A209833 a(f(A074773(n))) = A074773(n); 1 <= n <= 9999; f: N -> {1..9999}.
%C A209833 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 A209833 1. Run Rabin-Miller test only with base 2. If x not pass return composite.
%C A209833 2. Run Rabin-Miller test only with base 3. If x not pass return composite.
%C A209833 3. Run Rabin-Miller test only with base 5. If x not pass return composite.
%C A209833 4. Run Rabin-Miller test only with base 7. If x not pass return composite.
%C A209833 5. Compute i = f(x); if a(i) = x, return composite; otherwise return prime.
%C A209833 ---
%C A209833 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 A209833 Washington Bomfim, <a href="/A209833/a209833_1.txt">C:/temp/V.txt</a>
%H A209833 Washington Bomfim, <a href="/A209833/a209833_2.txt">C:/temp/A.txt</a>
%H A209833 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 A209833 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Rabin-MillerStrongPseudoprimeTest.html">Rabin-Miller Strong Pseudoprime Test</a>
%e A209833 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 A209833 (PARI)
%o A209833 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 A209833 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 A209833 \\
%o A209833 f(x)={y=V[x%453359393%M+1]; z=V[x%450577199%M+1]; return((y<=z)*z + (y>z)*y +1);};
%o A209833 \\
%o A209833 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 A209833 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 A209833 print("");a=vector(9999); for(i=1,9999,a[f(p[i])]=p[i]);for(i=1,9999, print(i," ",a[i]))
%Y A209833 Cf. A208846.
%K A209833 nonn,fini,full
%O A209833 1,1
%A A209833 _Washington Bomfim_, Mar 14 2012