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

 

Logo

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 56th year, we are closing in on 350,000 sequences, and we’ve crossed 9,700 citations (which often say “discovered thanks to the OEIS”).

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A283936 Number of "Euclidean primes" with respect to the first n primes. 0
2, 3, 5, 8, 13, 21, 32, 54, 83, 149, 251, 450, 807, 1481, 2696, 4968, 9155, 17143, 32009, 60024, 112785, 213193, 404285, 766690, 1456473, 2773176, 5292017, 10125044, 19403747 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,1

COMMENTS

Adleman, Pomerance and Rumely, in their 1983 primality testing paper, defined a "Euclidean prime" with respect to a finite set of primes P to be a prime q such that q-1 is squarefree and all the prime factors of q-1 are in P. In their paper they give the first 13 terms of this sequence.

REFERENCES

Yuri I. Manin and Alexei A. Panchishkin, "Introduction to Modern Number Theory: Fundamental Problems, Ideas and Theories", Springer, 2005, pp. 69-70.

A. N. Parshin and I. R. Shafarevich, "Number Theory I: Fundamental Problems, Ideas and Theories", Springer, 1995, pp. 53-54.

O. N. Vasilenko, "Number-theoretic Algorithms in Cryptography", American Mathematical Society, 2007, pp. 23-27.

Song Y. Yan, "Primality Testing and Integer Factorization in Public-Key Cryptography", Springer Science & Business Media, 2004, pp. 178-179.

LINKS

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

Leonard M. Adleman, Carl Pomerance, Robert S. Rumely, "On Distinguishing Prime Numbers from Composite Numbers", The Annals of Mathematics, 2nd Series, Vol. 117, No. 1, (Jan., 1983), pp. 173-206.

Robert Rumely, "Recent Advances in Primality Testing", Notices Amer. Math. Soc Vol. 30, No. 5 (1983), pp. 475-477.

EXAMPLE

For the first 3 primes, 2, 3 and 5, there are 5 Euclidean primes: 2, 2 + 1 = 3, 2*3 + 1 = 7, 2*5 + 1 = 11 and 2*3*5 + 1 = 31.

MATHEMATICA

Table[Count[Divisors@ Product[Prime@ i, {i, n}] + 1, d_ /; PrimeQ@ d], {n, 27}]

(* Second Program *)

Accumulate@ FoldList[{Count[Last@ #, d_ /; PrimeQ[d + 1]], Flatten@ #} &@ {Last@ #1, Prime[#2] Last@ #1} &, {0, {1}}, Range@ 24][[All, 1]] + 1 (* Michael De Vlieger, Mar 20 2017 *)

CROSSREFS

Sequence in context: A048817 A011185 A240733 * A278800 A334738 A286938

Adjacent sequences:  A283933 A283934 A283935 * A283937 A283938 A283939

KEYWORD

nonn,more

AUTHOR

Amiram Eldar, Mar 18 2017

EXTENSIONS

a(25)-a(29) from Michael De Vlieger, Mar 20 2017

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 December 3 18:19 EST 2021. Contains 349467 sequences. (Running on oeis4.)