|
|
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
|
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.
|
|
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
|
|
|
KEYWORD
|
nonn,more
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|