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

%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