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

%I A000945 M0863 N0329 #183 Mar 28 2025 04:54:45
%S A000945 2,3,7,43,13,53,5,6221671,38709183810571,139,2801,11,17,5471,52662739,
%T A000945 23003,30693651606209,37,1741,1313797957,887,71,7127,109,23,97,159227,
%U A000945 643679794963466223081509857,103,1079990819,9539,3143065813,29,3847,89,19,577,223,139703,457,9649,61,4357
%N A000945 Euclid-Mullin sequence: a(1) = 2, a(n+1) is smallest prime factor of 1 + Product_{k=1..n} a(k).
%C A000945 "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
%C A000945 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
%C A000945 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
%C A000945 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
%C A000945 Needs longer b-file. - _N. J. A. Sloane_, Dec 18 2015
%C A000945 A056756 gives the position of the k-th prime in this sequence for each k. - _Jianing Song_, May 07 2021
%C A000945 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
%C A000945 In Ribenboim 2004, a wrong value of a(8) is given, 6221271 instead of 6221671. - _Stefano Spezia_, Mar 27 2025
%D A000945 Richard Crandall and Carl Pomerance, Prime Numbers: A Computational Perspective, Springer, NY, 2001; see p. 6.
%D A000945 Richard Guy and Richard Nowakowski, Discovering primes with Euclid, Delta (Waukesha), Vol. 5, pp. 49-63, 1975.
%D A000945 Paulo Ribenboim, The Little Book of Bigger Primes, Springer-Verlag NY 2004. See p. 5.
%D A000945 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A000945 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D A000945 Samuel S. Wagstaff, Jr., Computing Euclid's primes, Bull. Institute Combin. Applications, Vol. 8 (1993), pp. 23-32.
%H A000945 Ryan Propper, <a href="/A000945/b000945.txt">Table of n, a(n) for n = 1..51</a> (first 47 terms from T. D. Noe)
%H A000945 Andrew R. Booker, <a href="https://doi.org/10.1515/integers-2012-0034">On Mullin's second sequence of primes</a>, Integers, Vol. 12, No. 6 (2012), pp. 1167-1177; <a href="https://arxiv.org/abs/1107.3318">arXiv preprint</a>, arXiv:1107.3318 [math.NT], 2011-2013.
%H A000945 Andrew R. Booker, <a href="https://arxiv.org/abs/1605.08929">A variant of the Euclid-Mullin sequence containing every prime</a>, arXiv preprint arXiv:1605.08929 [math.NT], 2016.
%H A000945 Andrew R. Booker and Sean A. Irvine, <a href="https://doi.org/10.1016/j.jnt.2016.01.013">The Euclid-Mullin graph</a>, Journal of Number Theory, Vol. 165 (2016), pp. 30-57; <a href="https://arxiv.org/abs/1508.03039">arXiv preprint</a>, arXiv:1508.03039 [math.NT], 2015-2016.
%H A000945 Cristian Cobeli and Alexandru Zaharescu, <a href="http://rms.unibuc.ro/bulletin/pdf/56-1/PromenadePascalPart1.pdf">Promenade around Pascal Triangle-Number Motives</a>, Bull. Math. Soc. Sci. Math. Roumanie, Vol. 56(104), No. 1 (2013), pp. 73-98.
%H A000945 Keith Conrad, <a href="https://kconrad.math.uconn.edu/blurbs/ugradnumthy/infinitudeofprimes.pdf">The infinitude of the primes</a>, University of Connecticut, 2020.
%H A000945 C. D. Cox and A. J. van der Poorten, <a href="http://dx.doi.org/10.1017/S1446788700006236">On a sequence of prime numbers</a>, Journal of the Australian Mathematical Society, Vol. 8 (1968), pp. 571-574.
%H A000945 FactorDB, <a href="http://factordb.com/index.php?showid=1100000000535556602">Status of EM51</a>.
%H A000945 Richard Guy and Richard Nowakowski, <a href="/A000945/a000945_5.pdf">Discovering primes with Euclid</a>, Research Paper No. 260 (Nov 1974), The University of Calgary Department of Mathematics, Statistics and Computing Science.
%H A000945 Lucas Hoogendijk, <a href="https://dspace.library.uu.nl/handle/1874/394848">Prime Generators</a>, Bachelor Thesis, Utrecht University (Netherlands, 2020).
%H A000945 Robert R. Korfhage, <a href="/A000945/a000945_3.pdf">On a sequence of prime numbers</a>, Bull Amer. Math. Soc., Vol. 70 (1964), pp. 341, 342, 747. [Annotated scanned copy]
%H A000945 Evelyn Lamb, <a href="https://blogs.scientificamerican.com/roots-of-unity/a-curious-sequence-of-prime-numbers/">A Curious Sequence of Prime Numbers</a>, Scientific American blog (2019).
%H A000945 Des MacHale, <a href="http://dx.doi.org/10.2307/3621650">Infinitely many proofs that there are infinitely many primes</a>, Math. Gazette, Vol. 97, No. 540 (2013), pp. 495-498.
%H A000945 Mersenne Forum, <a href="http://www.mersenneforum.org/showthread.php?p=207854#post207854">Factoring 43rd Term of Euclid-Mullin sequence</a>.
%H A000945 Mersenne Forum, <a href="http://www.mersenneforum.org/showthread.php?p=311145">Factoring EM47</a>.
%H A000945 Romeo Meštrović, <a href="http://arxiv.org/abs/1202.3670">Euclid's theorem on the infinitude of primes: a historical survey of its proofs (300 BC--2012) and another new proof</a>, arXiv preprint arXiv:1202.3670 [math.HO], 2012.
%H A000945 Albert A. Mullin, <a href="http://dx.doi.org/10.1090/S0002-9904-1963-11017-4">Research Problem 8: Recursive function theory</a>, Bull. Amer. Math. Soc., Vol. 69, No. 6 (1963), p. 737.
%H A000945 Thorkil Naur, <a href="/A000945/a000945.pdf">Letter to N. J. A. Sloane, Aug 27 1991</a>, together with copies of "Mullin's sequence of primes is not monotonic" (1984) and "New integer factorizations" (1983) [Annotated scanned copies]
%H A000945 OEIS wiki, <a href="https://oeis.org/wiki/OEIS_sequences_needing_factors">OEIS sequences needing factors</a>
%H A000945 Paul Pollack and Enrique Treviño, <a href="http://www.jstor.org/stable/10.4169/amer.math.monthly.121.05.433">The Primes that Euclid Forgot</a>, Amer. Math. Monthly, Vol. 121, No. 5 (2014), pp. 433-437. MR3193727; <a href="http://pollack.uga.edu/mullin.pdf">alternative link</a>.
%H A000945 Daphne Stouthart, <a href="https://studenttheses.uu.nl/handle/20.500.12932/47109">Euclid and the infinite number of missing primes</a>, Bachelor Thesis, Utrecht Univ (Netherlands, 2024). See p. 1.
%H A000945 Samuel S. Wagstaff, Jr., <a href="/A000945/a000945_1.pdf">Emails to N. J. A. Sloane, May 30 1991</a>.
%H A000945 Samuel S. Wagstaff, Jr., <a href="/A000945/a000945_4.pdf">Computing Euclid's primes</a>, Bull. Institute Combin. Applications, Vol. 8 (1993), pp. 23-32. (Annotated scanned copy)
%e A000945 a(5) is equal to 13 because 2*3*7*43 + 1 = 1807 = 13 * 139.
%p A000945 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);
%p A000945 # _Robert FERREOL_, Sep 25 2019
%t A000945 f[1]=2; f[n_] := f[n] = FactorInteger[Product[f[i], {i, 1, n - 1}] + 1][[1, 1]]; Table[f[n], {n, 1, 46}]
%t A000945 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 *)
%o A000945 (PARI) print1(k=2);for(n=2,20,print1(", ",p=factor(k+1)[1,1]);k*=p) \\ _Charles R Greathouse IV_, Jun 10 2011
%o A000945 (PARI) P=[];until(,print(P=concat(P,factor(vecprod(P)+1)[1,1]))) \\ _Jeppe Stig Nielsen_, Apr 01 2024
%Y A000945 Cf. A000946, A005265, A005266, A051309-A051334, A051614, A051615, A051616, A056756.
%K A000945 nonn,nice,hard
%O A000945 1,1
%A A000945 _N. J. A. Sloane_