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, Ann. Math. 2nd Series, 117(1) (Jan., 1983), 173-206.
Robert Rumely, Recent Advances in Primality Testing, Notices Amer. Math. Soc 30(5) (1983), 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}]
(* Alternative: *)
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
(SageMath)
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,changed
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
a(36)-a(39) from Robin Visser, May 01 2025
STATUS
approved