This site is supported by donations to The OEIS Foundation.



Annual Appeal: Please make a donation to keep the OEIS running. In 2018 we replaced the server with a faster one, added 20000 new sequences, and reached 7000 citations (often saying "discovered thanks to the OEIS").
Other ways to donate

(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000945 Euclid-Mullin sequence: a(1) = 2, a(n+1) is smallest prime factor of 1 + Product_{k=1..n} a(k).
(Formerly M0863 N0329)
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 (list; graph; refs; listen; history; text; internal format)



"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


R. Crandall and C. Pomerance, Prime Numbers: A Computational Perspective, Springer, NY, 2001; see p. 6.

R. K. Guy and R. Nowakowski, Discovering primes with Euclid, Delta (Waukesha), Vol. 5, pp. 49-63, 1975.

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).

S. S. Wagstaff, Jr., Computing Euclid's primes, Bull. Institute Combin. Applications, 8 (1993), 23-32.


T. D. Noe and Ryan Propper, Table of n, a(n) for n = 1..51 (first 47 terms from T. D. Noe)

A. R. Booker, On Mullin's second sequence of primes, arXiv preprint arXiv:1107.3318 [math.NT], 2011.

Andrew R. Booker, A variant of the Euclid-Mullin sequence containing every prime, arXiv preprint arXiv:1605.08929 [math.NT], 2016.

A. R. Booker, S. A. Irvine, The Euclid-Mullin graph, arXiv preprint arXiv:1508.03039 [math.NT], 2015.

C. Cobeli and A. Zaharescu, Promenade around Pascal Triangle-Number Motives, Bull. Math. Soc. Sci. Math. Roumanie, Tome 56(104) No. 1, 2013, 73-98.

C. D. Cox and A. J. van der Poorten, On a sequence of prime numbers, Journal of the Australian Mathematical Society 8 (1968), pp. 571-574.

R. K. Guy and R. Nowakowski, Discovering primes with Euclid, Research Paper No. 260 (Nov 1974), The University of Calgary Department of Mathematics, Statistics and Computing Science.

R. R. Khorfhage, On a sequence of prime numbers, Bull Amer. Math. Soc., 70 (1964), pp. 341, 342, 747. [Annotated scanned copy]

Des MacHale, Infinitely many proofs that there are infinitely many primes, Math. Gazette, 97 (No. 540, 2013), 495-498.

Mersenne Forum, Factoring 43rd Term of Euclid-Mullin sequence

Mersenne Forum, Factoring EM47

R. Mestrovic, 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.

A. A. Mullin, Research Problem 8: Recursive function theory, Bull. Amer. Math. Soc., 69 (1963), 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

P. Pollack and E. Trevino, The primes that Euclid forgot, 2013.

Paul Pollack, Enrique TreviƱo, The Primes that Euclid Forgot, Amer. Math. Monthly 121 (2014), no. 5, 433--437. MR3193727

S. S. Wagstaff, Jr., Emails to N. J. A. Sloane, May 30 1991

S. S. Wagstaff, Jr., Computing Euclid's primes, Bull. Institute Combin. Applications, 8 (1993), 23-32. (Annotated scanned copy)


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


f[1]=2; f[n_] := f[n] = FactorInteger[Product[f[i], {i, 1, n - 1}] + 1][[1, 1]]; Table[f[n], {n, 1, 46}]


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


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

Sequence in context: A265776 A163157 A260819 * A261564 A126263 A216826

Adjacent sequences:  A000942 A000943 A000944 * A000946 A000947 A000948




N. J. A. Sloane



Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 15 04:33 EST 2018. Contains 318141 sequences. (Running on oeis4.)