A283936 Number of "Euclidean primes" with respect to the first n primes.

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

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, and 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