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
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 *)
PROG
(Sage)
def a(n):
P, ans = Primes()[:n], 0
for i in range(2^n):
q = product([P[j] for j in range(n) if i&(1<<j)])
if (q+1).is_prime(): ans += 1
return ans # Robin Visser, May 25 2024
CROSSREFS
KEYWORD
nonn,more
AUTHOR
Amiram Eldar, Mar 18 2017
EXTENSIONS
a(25)-a(29) from Michael De Vlieger, Mar 20 2017
a(30)-a(35) from Robin Visser, May 25 2024
STATUS
approved