login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A211112 a(n) is the smallest pseudoprime q in A074773 such that f(q) = n, where f: N -> {1..63} is given below. 1
39365185894561, 52657210792621, 11377272352951, 15070413782971, 3343433905957, 16603327018981, 3461715915661, 52384617784801, 3477707481751, 18996486073489, 55712149574381, 118670087467 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,1

COMMENTS

Also, list of the 63 smallest strong pseudoprimes to bases 2,3,5, and 7, indexed by function f. See the expression of f in the first PARI program.

We can use the algorithm given below to make a primality test to see if an integer x, x < A074773(64) = 60153869469241, is prime.

1. Run Miller-Rabin test with base 2, if x is not prime return composite.

2. Run Miller-Rabin test with base 3, if x is not prime return composite.

3. Run Miller-Rabin test with base 5, if x is not prime return composite.

4. Run Miller-Rabin test with base 7, if x is not prime return composite.

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

In first reference, pp 1022, there is a test where a table of strong pseudoprimes is used. Terms computed using data from Charles R Greathouse IV. See A074773. Second link references the file "C:/temp/A074773.txt" used by the first PARI program. This file is a string with the first 63 terms of A074773, each term preceded by its number of digits.

LINKS

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

Washington Bomfim, A.txt

C. Pomerance, J. L. Selfridge, and S. S. Wagstaff, Jr., The pseudoprimes to 25*10^9, Mathematics of Computation 35 (1980), pp. 1003-1026.

Wikipedia, Miller-Rabin primality test

EXAMPLE

Because f(A074773(15)) = 5, a(5) = A074773(15).

PROG

(PARI)

f(x)={ f1=x % 20650997 % 63; f2=x % 13936751 % 63; v1=3521775543809890147;

v2 = 1700305497776372630; v3 = 4844350019353692337;

h1=(f1<=20)*((v1>>(3*f1))%8)+(f1>=42)*((v3>>(3*(f1-42)))%8)+(f1>20&&f1<42)*((v2>>(3*(f1-21)))%8);

h2=(f2<=20)*((v1>>(3*f2))%8)+(f2>=42)*((v3>>(3*(f2-42)))%8)+(f2>20&&f2<42)*((v2>>(3*(f2-21)))%8);

y = (h1==h2)*f2 + (h1>h2)*f1+(h2>h1)*f2 + 1; return (y); };

\\

s=Str(read("C:/temp/A074773.txt" )); x=Vec(s); n=0; k=0; j=0; i=1; p=vector(63); y=0;

for(n=1, 63, 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);

a=vector(63); for(i=1, 63, y =f(p[i]); a[y]=p[i]); for(i=1, 63, print(i, " ", a[i]));

CROSSREFS

Cf. A074773, A208847, A210588.

Sequence in context: A122126 A318575 A337915 * A132389 A186913 A262193

Adjacent sequences:  A211109 A211110 A211111 * A211113 A211114 A211115

KEYWORD

nonn,fini,full

AUTHOR

Washington Bomfim, Apr 11 2012

EXTENSIONS

Edited by M. F. Hasler, Dec 09 2016 and Dec 17 2016

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 25 15:27 EDT 2021. Contains 347658 sequences. (Running on oeis4.)