|
%I #32 May 25 2024 20:53:26
%S 2,3,5,8,13,21,32,54,83,149,251,450,807,1481,2696,4968,9155,17143,
%T 32009,60024,112785,213193,404285,766690,1456473,2773176,5292017,
%U 10125044,19403747,37237818,71513387,137531053,264800069,510634602,985451509
%N Number of "Euclidean primes" with respect to the first n primes.
%C 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.
%D Yuri I. Manin and Alexei A. Panchishkin, "Introduction to Modern Number Theory: Fundamental Problems, Ideas and Theories", Springer, 2005, pp. 69-70.
%D A. N. Parshin and I. R. Shafarevich, "Number Theory I: Fundamental Problems, Ideas and Theories", Springer, 1995, pp. 53-54.
%D O. N. Vasilenko, "Number-theoretic Algorithms in Cryptography", American Mathematical Society, 2007, pp. 23-27.
%D Song Y. Yan, "Primality Testing and Integer Factorization in Public-Key Cryptography", Springer Science & Business Media, 2004, pp. 178-179.
%H Leonard M. Adleman, Carl Pomerance, and Robert S. Rumely, <a href="https://www.jstor.org/stable/2006975">On Distinguishing Prime Numbers from Composite Numbers</a>, The Annals of Mathematics, 2nd Series, Vol. 117, No. 1, (Jan., 1983), pp. 173-206.
%H Robert Rumely, <a href="https://www.ams.org/journals/notices/198308/198308FullIssue.pdf">Recent Advances in Primality Testing</a>, Notices Amer. Math. Soc Vol. 30, No. 5 (1983), pp. 475-477.
%e 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.
%t Table[Count[Divisors@ Product[Prime@ i, {i, n}] + 1, d_ /; PrimeQ@ d], {n, 27}]
%t (* Second Program *)
%t 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 *)
%o (Sage)
%o def a(n):
%o P, ans = Primes()[:n], 0
%o for i in range(2^n):
%o q = product([P[j] for j in range(n) if i&(1<<j)])
%o if (q+1).is_prime(): ans += 1
%o return ans # _Robin Visser_, May 25 2024
%K nonn,more
%O 1,1
%A _Amiram Eldar_, Mar 18 2017
%E a(25)-a(29) from _Michael De Vlieger_, Mar 20 2017
%E a(30)-a(35) from _Robin Visser_, May 25 2024
|
