A051334 -id:A051334 - cp's OEIS frontend

A000945 Euclid-Mullin sequence: a(1) = 2, a(n+1) is smallest prime factor of 1 + Product_{k=1..n} a(k).

2, 3, 7, 43, 13, 53, 5, 6221671, 38709183810571, 139, 2801, 11, 17, 5471, 52662739, 23003, 30693651606209, 37, 1741, 1313797957, 887, 71, 7127, 109, 23, 97, 159227, 643679794963466223081509857, 103, 1079990819, 9539, 3143065813, 29, 3847, 89, 19, 577, 223, 139703, 457, 9649, 61, 4357

Offset: 1

N. J. A. Sloane

"Does the sequence ... contain every prime? ... [It] was considered by Guy and Nowakowski and later by Shanks, [Wagstaff 1993] computed the sequence through the 43rd term. The computational problem inherent in continuing the sequence further is the enormous size of the numbers that must be factored. Already the number a(1)* ... *a(43) + 1 has 180 digits." - Crandall and Pomerance
If this variant of Euclid-Mullin sequence is initiated either with 3, 7 or 43 instead of 2, then from a(5) onwards it is unchanged. See also A051614. - Labos Elemer, May 03 2004
Wilfrid Keller informed me that a(1)* ... *a(43) + 1 was factored as the product of two primes on Mar 09 2010 by the GNFS method. See the post in the Mersenne Forum for more details. The smaller 68-digit prime is a(44). Terms a(45)-a(47) were easy to find. Finding a(48) will require the factorization of a 256-digit number. See the b-file for the four new terms. - T. D. Noe, Oct 15 2010
On Sep 11 2012, Ryan Propper factored the 256-digit number by finding a 75-digit factor by using ECM. Finding a(52) will require the factorization of a 335-digit number. See the b-file for the terms a(48) to a(51). - V. Raman, Sep 17 2012
Needs longer b-file. - N. J. A. Sloane, Dec 18 2015
A056756 gives the position of the k-th prime in this sequence for each k. - Jianing Song, May 07 2021
Named after the Greek mathematician Euclid (flourished c. 300 B.C.) and the American engineer and mathematician Albert Alkins Mullin (1933-2017). - Amiram Eldar, Jun 11 2021
In Ribenboim 2004, a wrong value of a(8) is given, 6221271 instead of 6221671. - Stefano Spezia, Mar 27 2025

			a(5) is equal to 13 because 2*3*7*43 + 1 = 1807 = 13 * 139.

Richard Crandall and Carl Pomerance, Prime Numbers: A Computational Perspective, Springer, NY, 2001; see p. 6.
Richard Guy and Richard Nowakowski, Discovering primes with Euclid, Delta (Waukesha), Vol. 5, pp. 49-63, 1975.
Paulo Ribenboim, The Little Book of Bigger Primes, Springer-Verlag NY 2004. See p. 5.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
Samuel S. Wagstaff, Jr., Computing Euclid's primes, Bull. Institute Combin. Applications, Vol. 8 (1993), pp. 23-32.

Ryan Propper, Table of n, a(n) for n = 1..51 (first 47 terms from T. D. Noe)
Andrew R. Booker, On Mullin's second sequence of primes, Integers, Vol. 12, No. 6 (2012), pp. 1167-1177; arXiv preprint, arXiv:1107.3318 [math.NT], 2011-2013.
Andrew R. Booker, A variant of the Euclid-Mullin sequence containing every prime, arXiv preprint arXiv:1605.08929 [math.NT], 2016.
Andrew R. Booker and Sean A. Irvine, The Euclid-Mullin graph, Journal of Number Theory, Vol. 165 (2016), pp. 30-57; arXiv preprint, arXiv:1508.03039 [math.NT], 2015-2016.
Cristian Cobeli and Alexandru Zaharescu, Promenade around Pascal Triangle-Number Motives, Bull. Math. Soc. Sci. Math. Roumanie, Vol. 56(104), No. 1 (2013), pp. 73-98.
Keith Conrad, The infinitude of the primes, University of Connecticut, 2020.
C. D. Cox and A. J. van der Poorten, On a sequence of prime numbers, Journal of the Australian Mathematical Society, Vol. 8 (1968), pp. 571-574.
FactorDB, Status of EM51.
Richard Guy and Richard Nowakowski, Discovering primes with Euclid, Research Paper No. 260 (Nov 1974), The University of Calgary Department of Mathematics, Statistics and Computing Science.
Lucas Hoogendijk, Prime Generators, Bachelor Thesis, Utrecht University (Netherlands, 2020).
Robert R. Korfhage, On a sequence of prime numbers, Bull Amer. Math. Soc., Vol. 70 (1964), pp. 341, 342, 747. [Annotated scanned copy]
Evelyn Lamb, A Curious Sequence of Prime Numbers, Scientific American blog (2019).
Des MacHale, Infinitely many proofs that there are infinitely many primes, Math. Gazette, Vol. 97, No. 540 (2013), pp. 495-498.
Mersenne Forum, Factoring 43rd Term of Euclid-Mullin sequence.
Mersenne Forum, Factoring EM47.
Romeo Meštrović, Euclid's theorem on the infinitude of primes: a historical survey of its proofs (300 BC--2012) and another new proof, arXiv preprint arXiv:1202.3670 [math.HO], 2012.
Albert A. Mullin, Research Problem 8: Recursive function theory, Bull. Amer. Math. Soc., Vol. 69, No. 6 (1963), p. 737.
Thorkil Naur, Letter to N. J. A. Sloane, Aug 27 1991, together with copies of "Mullin's sequence of primes is not monotonic" (1984) and "New integer factorizations" (1983) [Annotated scanned copies]
OEIS wiki, OEIS sequences needing factors
Paul Pollack and Enrique Treviño, The Primes that Euclid Forgot, Amer. Math. Monthly, Vol. 121, No. 5 (2014), pp. 433-437. MR3193727; alternative link.
Daphne Stouthart, Euclid and the infinite number of missing primes, Bachelor Thesis, Utrecht Univ (Netherlands, 2024). See p. 1.
Samuel S. Wagstaff, Jr., Emails to N. J. A. Sloane, May 30 1991.
Samuel S. Wagstaff, Jr., Computing Euclid's primes, Bull. Institute Combin. Applications, Vol. 8 (1993), pp. 23-32. (Annotated scanned copy)

Cf. A000946, A005265, A005266, A051309-A051334, A051614, A051615, A051616, A056756.

a :=n-> if n = 1 then 2 else numtheory:-divisors(mul(a(i),i = 1 .. n-1)+1)[2] fi: seq(a(n), n=1..15);
# Robert FERREOL, Sep 25 2019

f[1]=2; f[n_] := f[n] = FactorInteger[Product[f[i], {i, 1, n - 1}] + 1][[1, 1]]; Table[f[n], {n, 1, 46}]
nxt[{p_,a_}]:=With[{c=FactorInteger[p+1][[1,1]]},{p*c,c}]; Rest[NestList[nxt,{1,2},20][[;;,2]]] (* Harvey P. Dale, Feb 02 2025 *)

print1(k=2);for(n=2,20,print1(", ",p=factor(k+1)[1,1]);k*=p) \\ Charles R Greathouse IV, Jun 10 2011

P=[];until(,print(P=concat(P,factor(vecprod(P)+1)[1,1]))) \\ Jeppe Stig Nielsen, Apr 01 2024

A093777 a(n) is the smallest prime which, if used to start a Euclid-Mullin sequence (like A000945), the resulting sequence contains the n consecutive primes 2, 3, ..., prime(n).

Original entry on oeis.org

2, 2, 19, 199, 2089, 99109, 1960969, 10129129, 87726649, 4549584049, 328034245549, 20584643748679, 666188861477149, 31395465477725359, 894857713367947339, 434392154438254391389, 17934770256689308411399

Offset: 1

Labos Elemer, May 03 2004

nonn

Thanks in part to Dirichlet's theorem, a(n) exists for each n. - Don Reble, Oct 07 2006

			a(1) = a(2) = 2 because they generate {2,3,7,43,13,...};
a(3) = 19 because it generates {19,2,3,5,571,271,...}, see A051312;
a(4) = 199 because it generates {199,2,3,5,7,23,881,...};
a(5) = 2089 because it generates {2089,2,3,5,7,11,269,...};
a(6) = 99109 because it generates {99109,2,3,5,7,11,13,2976243271,...};
a(7) = 1960969 because it generates {1960969,2,3,5,7,11,13,17,281,47,419,5539788476533581271,37,19,173,...}

Toshitaka Suzuki, Table of n, a(n) for n = 1..100

Cf. A093778, A093779, A093780, A000945, A051309-A051334, A051614-A051616, A056756.

More terms from Don Reble, Oct 07 2006

A093778 Primes p used as initial values for Euclid-Mullin sequences (variant A000945) instead of 2, such that all provide {p,2,3,5,7,11,13,q,...} initial segments in which the first six primes occur from 2nd to 7th terms.

Original entry on oeis.org

99109, 159169, 189199, 399409, 459469, 609619, 669679, 699709, 819829, 1030039, 1090099, 1150159, 1270279, 1300309, 1390399, 1420429, 1810819, 1870879, 1930939, 1960969, 2021029, 2051059, 2141149, 2201209, 2261269, 2321329

Offset: 1

Labos Elemer, May 03 2004

nonn

			Initial segments of Euclid-Mullin sequences provided by
a[33]=3132139, a[34] and a[35] initial values:
{3132139,2,3,5,7,11,13,94058134171}}
{3282289,2,3,5,7,11,13,59}},
{3372379,2,3,5,7,11,13,29}}

Cf. A000945, A051308-A051334, A056756, A093777.

b[x_] :=First[Flatten[FactorInteger[Apply[Times, Table[b[j], {j, 1, x - 1}]] +1]]];b[1] = 1; Do[b[1] = Prime[j], el=8; If[Equal[Table[b[w], {w, 2, 7}], {2, 3, 5, 7, 11, 13}], Print[{j, Table[b[w], {w, 1, el}]}]], {j, 100000, 1000000}]

A093782 a(n) is the smallest initial value (a prime) for the Euclid-Mullin (EM) sequence in which the p=5 prime emerges as n-th term, i.e., arises at the n-th position.

Original entry on oeis.org

5, 0, 17, 19, 127, 61, 2, 31, 97, 13, 23, 269, 53, 239, 181, 449, 541, 11, 953, 1741, 179, 1889, 823, 3209, 13619, 383, 6971, 10331, 45959, 13721

Offset: 1

Labos Elemer, May 04 2004

The sequence is not monotonic and it seems that p=5 may arise at any position > 2. a(2)=0 means that 5 is never the 2nd term in an EM sequence of A000945-type because a(2)=2 or 3.

a(31)>=8581. [Sean A. Irvine, Oct 31 2011]

			The sequence for 17 is 17, 2, 5, ... where the 5 is at the third place, therefore a(3)=17.
For n=15 we have the sequence 181, 2, 3, 1087, 73, 7, 29, 151, 61, 98689, 11, 10929259909, 678859, 97, 5, ...
a(16) = 449 uses the sequence 449, 2, 29, 3, 7, 349, 190861819, 166273, 16091, 11, 3807491, 53, 17, 313, 23, 5, ...
The sequence for 11 is 11, 2, 23, 3, 7, 13, 10805892983887, 73, 6397, 19, 489407, 2753, 87491, 18618443, 5, ... with the 5 at the 18th place, so a(18)=11.

Cf. A000945, A051308-A051334, A056756, A093777-A093781.

Corrected by R. J. Mathar, Oct 06 2006
a(16) = 449 was conjectured by R. J. Mathar and confirmed by Don Reble, Oct 07 2006
a(19)-a(24) from David Wasserman, Apr 20 2007
a(25)-a(30) from Sean A. Irvine, Oct 30 2011

A094152 a(n) is the position of prime 7 in the Euclid-Mullin (EM) sequence of type A000945, if it were started with prime(n) instead of 2.

Original entry on oeis.org

3, 3, 15, 1, 5, 6, 5, 24, 10, 6, 7, 6, 5, 4, 7, 5, 3, 5, 6, 16, 5, 6, 5, 28, 6, 3, 5, 36, 7, 15, 4, 15, 7, 7, 8, 7, 7, 5, 7, 14, 5, 6, 19, 16, 17, 5, 4, 12, 5, 8, 10, 17, 5, 5, 8, 10, 3, 5, 7, 30, 5, 5, 20, 3, 5, 6, 6, 4, 9, 9, 3, 9, 5, 6, 8, 8

Offset: 1

Labos Elemer, May 05 2004

nonn

			n=8: p(8)=19, the corresponding EM sequence is A051312 in which p=7 arises at the 24th position as follows:
{19, 2, 3, 5, 571, 271, 457, 397, 1123, 23, 103, 42572757267735264511, 313, 17, 16013177, 7951, 1259, 41, 1531, 11, 83, 53, 67, 7, 21397}, thus a(8)=24.

Sean A. Irvine, Table of n, a(n) for n = 1..3505

Cf. A000945, A051308-A051334, A056756, A093777-A093784.

More terms from Sean A. Irvine, Sep 20 2012

A094153 a(n) is least prime p such that 7 is the n-th term in the Euclid-Mullin sequence starting at p, or 0 if no such prime p exists.

Original entry on oeis.org

7, 0, 2, 43, 11, 13, 31, 149, 347, 23, 439, 223, 461, 173, 5, 71, 197, 1153, 191, 307, 1657, 971, 9473, 19, 2399, 1607, 6781, 89, 9187, 281, 23623, 15077, 25579, 17203

Offset: 1

Labos Elemer, May 05 2004

The sequence is not monotonic. Compare to A093882.

Next term exceeds 50000. - Sean A. Irvine, Jan 12 2012

			a(5)=11 because p=7 first arises in EM at position 5, which is initiated with 11: {11,2,23,3,7,10627,433}; see A051309.

Cf. A000945, A051308-A051334, A056756, A093777-A093783.

Definition clarified, terms corrected and extended by Sean A. Irvine, Apr 15 2011
More terms from Sean A. Irvine, May 22 2011
25579 and 17203 from Sean A. Irvine, Jan 11 2012

A093779 a(n) is the position of prime 3 in the Euclid-Mullin (EM) sequence of type A000945, if it were started with prime(n) instead of 2.

Original entry on oeis.org

2, 1, 4, 3, 4, 3, 4, 3, 4, 4, 3, 3, 4, 3, 4, 4, 5, 3, 3, 4, 3, 3, 4, 4, 3, 5, 3, 4, 3, 4, 3, 4, 4, 3, 5, 3, 3, 3, 4, 4, 4, 3, 4, 3, 4, 3, 3, 3, 4, 3, 4, 4, 3, 4, 4, 4, 5, 3, 3, 4, 3, 4, 3, 5, 3, 4, 3, 3, 4, 3, 5, 4, 3, 3, 3, 5, 5, 3, 4, 3, 4, 3, 4, 3, 3, 4, 4, 3, 5, 3, 4, 6, 3, 4, 3, 5, 4, 5, 3, 3, 3, 4, 5, 4, 3

Offset: 1

Labos Elemer, May 03 2004

nonn

			p=3 arises first as n-th term for n=1,2,3,4 as follows: {3,2,7,43,13,53,5}, {2,3,7,43,13,53,5}, {7,2,3,43,13,53,5}, {5,2,11,3,331,19}, ... i.e., started at suitable initial primes;
p=2 arises always as 2nd or once as first term in case of various EM-sequences.

Cf. A000945, A051308-A051334, A056756, A093777, A093778.

A093780 a(n) is the smallest prime used as initial value for Euclid-Mullin (EM) sequence (of variant A000945), such that in the corresponding EM-sequence the p=3 prime arises at the n-th position.

Original entry on oeis.org

3, 2, 7, 5, 59, 479, 821, 1871, 17393, 43019, 284783, 1572149, 2737793, 32938853, 24254639

Offset: 1

Labos Elemer, May 03 2004

			p=3 arises first as n-th term for n=1,2,3,4,...,9th as follows:
{3,2,7,43,13,53,5},{2,3,7,43,13,53,5},{7,2,3,43,13,53,5},
{5,2,11,3,331,19},{269,2,7,3767,3,42559567},{479,2,7,19,5,3},
{821,2,31,109,7,509,3},{1871,2,19,7,37,13,23,3},
{17393,2,43,37,7,4129,13,5,3},

Cf. A000945, A051308-A051334, A056756, A093777-A093779.

More terms from David Wasserman, Apr 12 2007

A093781 a(n) is the position of the prime 5 in the Euclid-Mullin (EM) sequence of type A000945, if it were started with prime(n) instead of 2.

Original entry on oeis.org

7, 7, 1, 7, 18, 10, 3, 4, 11, 7, 8, 8, 10, 7, 3, 13, 8, 6, 7, 8, 6, 4, 7, 8, 9, 4, 6, 3, 4, 11, 5, 8, 3, 4, 4, 8, 8, 13, 3, 10, 21, 15, 6, 8, 3, 4, 13, 5, 3, 4, 8, 14, 6, 10, 3, 6, 12, 6, 10, 6, 6, 13, 8, 4, 6, 3, 11, 5, 3, 4, 13, 6, 10, 8, 4, 26, 8, 7, 11, 4, 7, 10, 7, 5, 4, 7, 16, 8, 7, 9, 3, 5, 5, 6

Offset: 1

Labos Elemer, May 04 2004

nonn

a(38) = 13 because prime(38) = 163 and the corresponding EM sequence is {163, 2, 3, 11, 7, 75307, 3931, 5399, 3041, 409, 179, 92958641873, 5, 2003, ...}, where 5 appears at the 13th position. - David Wasserman, Apr 19 2007

David Wasserman, Apr 19 2007, Table of n, a(n) for n = 1..1000

Cf. A000945, A051308-A051334, A056756, A093777-A093780.

Cf. A093782.

em(i) = local(p, c, n, f, q); p = prime(i); if (p == 5, return(1)); c = 1; n = p; while (1, c++; f = factor(n + 1, 2^31 - 1); q = f[1, 1]; if (!isprime(q), f = factor(n + 1); q = f[1, 1]); if (q == 5, return(c)); n *= q); \\ David Wasserman, Apr 19 2007

More terms from David Wasserman, Apr 19 2007

A094464 Least initial value for a Euclid/Mullin sequence whose 3rd term (= least prime divisor of 1+2p) equals the n-th prime. prime(1)=2 is never a third term, so offset=2.

Original entry on oeis.org

7, 17, 2, 5, 149, 263, 389, 11, 449, 821, 1091, 881, 1913, 23, 2729, 29, 2531, 6599, 2591, 6971, 3989, 41, 4583, 5189, 7019, 7673, 53, 13679, 7853, 8699, 12641, 9521, 13691, 12143, 19403, 13109, 22901, 83, 18251, 89, 20543, 32183, 23063, 26693

Offset: 2

Labos Elemer, May 10 2004

nonn

These primes are congruent to (prime(n)-1)/2 mod prime(n) if n > 4. Presumably all primes occur as 3rd term if initial prime is suitably chosen.

			n=25: prime(25) = 97 and an Euclid-Mullin sequence started with a(25) = 5189 = 97*53 + 48 is {5189, 2, 97, 101, 3, 7, 167, 356568143863}.
All larger (prime) solutions with 97 as 3rd term have the form 97k + 48 form. However, not all primes of the form 97k + 48 result in Euclid-Mullin (EM) sequences with the property that the 3rd term is 97. For example, 727 = 7*97 + 48 is a prime providing an EM sequence as follows: {727, 2, 3, 4363, 19, 5, 1709, 11, 33988283132431, 7} with 3rd term = 3.
Analogous statements hold for other initial or 3rd primes.

Cf. A000945, A051308-A051334, A094460.

a[x_]:=First[Flatten[FactorInteger[Apply[Times, Table[a[j], {j, 1, x-1}]]+1]]]; ta=Table[0, {20000}];a[1]=1;Do[{a[1]=Prime[j], el=3}; ta[[j]]=a[el], {j, 1, 20000}] Table[Prime[Min[Flatten[Position[ta, Prime[w]]]]], {w, 1, 100}]

a(n) = Min[x; A094460(x) = prime(n)].

cp's OEIS Frontend

A000945 Euclid-Mullin sequence: a(1) = 2, a(n+1) is smallest prime factor of 1 + Product_{k=1..n} a(k).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

A093777 a(n) is the smallest prime which, if used to start a Euclid-Mullin sequence (like A000945), the resulting sequence contains the n consecutive primes 2, 3, ..., prime(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A093778 Primes p used as initial values for Euclid-Mullin sequences (variant A000945) instead of 2, such that all provide {p,2,3,5,7,11,13,q,...} initial segments in which the first six primes occur from 2nd to 7th terms.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

A093782 a(n) is the smallest initial value (a prime) for the Euclid-Mullin (EM) sequence in which the p=5 prime emerges as n-th term, i.e., arises at the n-th position.

Views

Author

Keywords

Comments

Examples

Crossrefs

Extensions

A094152 a(n) is the position of prime 7 in the Euclid-Mullin (EM) sequence of type A000945, if it were started with prime(n) instead of 2.

Views

Author

Keywords

Examples

Links

Crossrefs

Extensions

A094153 a(n) is least prime p such that 7 is the n-th term in the Euclid-Mullin sequence starting at p, or 0 if no such prime p exists.

Views

Author

Keywords

Comments

Examples

Crossrefs

Extensions

A093779 a(n) is the position of prime 3 in the Euclid-Mullin (EM) sequence of type A000945, if it were started with prime(n) instead of 2.

Views

Author

Keywords

Examples

Crossrefs

A093780 a(n) is the smallest prime used as initial value for Euclid-Mullin (EM) sequence (of variant A000945), such that in the corresponding EM-sequence the p=3 prime arises at the n-th position.

Views

Author

Keywords

Examples

Crossrefs

Extensions

A093781 a(n) is the position of the prime 5 in the Euclid-Mullin (EM) sequence of type A000945, if it were started with prime(n) instead of 2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Extensions

A094464 Least initial value for a Euclid/Mullin sequence whose 3rd term (= least prime divisor of 1+2p) equals the n-th prime. prime(1)=2 is never a third term, so offset=2.