|
%I M0863 N0329 #169 Apr 04 2024 10:35:05
%S 2,3,7,43,13,53,5,6221671,38709183810571,139,2801,11,17,5471,52662739,
%T 23003,30693651606209,37,1741,1313797957,887,71,7127,109,23,97,159227,
%U 643679794963466223081509857,103,1079990819,9539,3143065813,29,3847,89,19,577,223,139703,457,9649,61,4357
%N Euclid-Mullin sequence: a(1) = 2, a(n+1) is smallest prime factor of 1 + Product_{k=1..n} a(k).
%C "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 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 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 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 Needs longer b-file. - _N. J. A. Sloane_, Dec 18 2015
%C A056756 gives the position of the k-th prime in this sequence for each k. - _Jianing Song_, May 07 2021
%C 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
%D Richard Crandall and Carl Pomerance, Prime Numbers: A Computational Perspective, Springer, NY, 2001; see p. 6.
%D Richard Guy and Richard Nowakowski, Discovering primes with Euclid, Delta (Waukesha), Vol. 5, pp. 49-63, 1975.
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D Samuel S. Wagstaff, Jr., Computing Euclid's primes, Bull. Institute Combin. Applications, Vol. 8 (1993), pp. 23-32.
%H 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 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 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 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 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 Keith Conrad, <a href="https://kconrad.math.uconn.edu/blurbs/ugradnumthy/infinitudeofprimes.pdf">The infinitude of the primes</a>, University of Connecticut, 2020.
%H 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 FactorDB, <a href="http://factordb.com/index.php?showid=1100000000535556602">Status of EM51</a>.
%H 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 Lucas Hoogendijk, <a href="https://dspace.library.uu.nl/handle/1874/394848">Prime Generators</a>, Bachelor Thesis, Utrecht University (Netherlands, 2020).
%H 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 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 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 Mersenne Forum, <a href="http://www.mersenneforum.org/showthread.php?p=207854#post207854">Factoring 43rd Term of Euclid-Mullin sequence</a>.
%H Mersenne Forum, <a href="http://www.mersenneforum.org/showthread.php?p=311145">Factoring EM47</a>.
%H 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 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 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 OEIS wiki, <a href="https://oeis.org/wiki/OEIS_sequences_needing_factors">OEIS sequences needing factors</a>
%H 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 Samuel S. Wagstaff, Jr., <a href="/A000945/a000945_1.pdf">Emails to N. J. A. Sloane, May 30 1991</a>.
%H 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 a(5) is equal to 13 because 2*3*7*43 + 1 = 1807 = 13 * 139.
%p 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 # _Robert FERREOL_, Sep 25 2019
%t f[1]=2; f[n_] := f[n] = FactorInteger[Product[f[i], {i, 1, n - 1}] + 1][[1, 1]]; Table[f[n], {n, 1, 46}]
%o (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 (PARI) P=[];until(,print(P=concat(P,factor(vecprod(P)+1)[1,1]))) \\ _Jeppe Stig Nielsen_, Apr 01 2024
%Y Cf. A000946, A005265, A005266, A051309-A051334, A051614, A051615, A051616, A056756.
%K nonn,nice,hard
%O 1,1
%A _N. J. A. Sloane_
|
