The Euclid-Mullin graph

Article, Preprint English OPEN
Booker, Andrew R.; Irvine, Sean A.;
  • Journal: volume 165,pages30-57issn: 0022-314X
  • Publisher copyright policies & self-archiving
  • Related identifiers: doi: 10.1016/j.jnt.2016.01.013
  • Subject: Prime numbers | Euclid–Mullin sequence | Mathematics - Number Theory
    arxiv: Mathematics::History and Overview | Mathematics::General Mathematics | Astrophysics::Cosmology and Extragalactic Astrophysics | Astrophysics::Instrumentation and Methods for Astrophysics

We introduce the Euclid-Mullin graph, which encodes all instances of Euclid's proof of the infinitude of primes. We investigate structural properties of the graph both theoretically and numerically; in particular, we prove that it is not a tree.
  • References (15)
    15 references, page 1 of 2

    1. Andrew R. Booker, On Mullin's second sequence of primes, Integers 12A (2012).

    2. Andrew R. Booker and T. D. Browning, Square-free values of reducible polynomials, preprint (2015), available at

    3. Johannes Buchmann and Ulrich Vollmer, Binary quadratic forms, Algorithms and Computation in Mathematics, vol. 20, Springer, Berlin, 2007, An algorithmic approach. MR 2300780 (2008b:11046)

    4. Chris Monico et al., GGNFS, available at

    5. Jason Papadopoulos et al., msieve, available at

    6. Ben Buhrow et al., YAFU, available at

    7. Paul Zimmermann et al., GMP-ECM, available at

    8. H. Halberstam, On the distribution of additive number-theoretic functions. II, J. London Math. Soc. 31 (1956), 1{14. MR 0073626 (17,461d)

    9. Nobushige Kurokawa and Takakazu Satoh, Euclid prime sequences over unique factorization domains, Experiment. Math. 17 (2008), no. 2, 145{152. MR 2433881 (2009k:11200)

    10. Dan Levy, The irreducible factorization of Fibonacci polynomials over Q, Fibonacci Quart. 39 (2001), no. 4, 309{319. MR 1851529 (2002f:11016)

  • Related Research Results (2)
  • Metrics
Share - Bookmark