Empirical verification of the even Goldbach conjecture and computation of prime gaps up to $4\cdot 10^{18}$
HTML articles powered by AMS MathViewer
- by Tomás Oliveira e Silva, Siegfried Herzog and Silvio Pardi;
- Math. Comp. 83 (2014), 2033-2060
- DOI: https://doi.org/10.1090/S0025-5718-2013-02787-1
- Published electronically: November 18, 2013
- PDF | Request permission
Abstract:
This paper describes how the even Goldbach conjecture was confirmed to be true for all even numbers not larger than $4\cdot 10^{18}$. Using a result of Ramaré and Saouter, it follows that the odd Goldbach conjecture is true up to $8.37\cdot 10^{26}$. The empirical data collected during this extensive verification effort, namely, counts and first occurrences of so-called minimal Goldbach partitions with a given smallest prime and of gaps between consecutive primes with a given even gap, are used to test several conjectured formulas related to prime numbers. In particular, the counts of minimal Goldbach partitions and of prime gaps are in excellent accord with the predictions made using the prime $k$-tuple conjecture of Hardy and Littlewood (with an error that appears to be $O(\sqrt {t\log \log t})$, where $t$ is the true value of the quantity being estimated). Prime gap moments also show excellent agreement with a generalization of a conjecture made in $1982$ by Heath-Brown.References
- Ralph G. Archibald, Goldbach’s theorem, Scripta Mathematica 3 (1935), 44–50, 153–161.
- A. O. L. Atkin and D. J. Bernstein, Prime sieves using binary quadratic forms, Math. Comp. 73 (2004), no. 246, 1023–1030. MR 2031423, DOI 10.1090/S0025-5718-03-01501-1
- Carter Bays and Richard H. Hudson, The segmented sieve of Eratosthenes and primes in arithmetic progressions to $10^{12}$, Nordisk Tidskr. Informationsbehandling (BIT) 17 (1977), no. 2, 121–127. MR 447090, DOI 10.1007/bf01932283
- Jan Bohman and Carl-Erik Fröberg, Numerical results on the Goldbach conjecture, Nordisk Tidskr. Informationsbehandling (BIT) 15 (1975), no. 3, 239–243. MR 389814, DOI 10.1007/bf01933655
- Richard P. Brent, The first occurrence of large gaps between successive primes, Math. Comp. 27 (1973), 959–963. MR 330021, DOI 10.1090/S0025-5718-1973-0330021-0
- Richard P. Brent, The distribution of small gaps between successive primes, Math. Comp. 28 (1974), 315–324. MR 330017, DOI 10.1090/S0025-5718-1974-0330017-X
- Harald Cramér, On the order of magnitude of the difference between consecutive prime numbers, Acta Arithmetica II (1937), 23–46.
- M. Deléglise and J. Rivat, Computing $\pi (x)$: the Meissel, Lehmer, Lagarias, Miller, Odlyzko method, Math. Comp. 65 (1996), no. 213, 235–245. MR 1322888, DOI 10.1090/S0025-5718-96-00674-6
- Marc Deléglise, Pierre Dusart, and Xavier-François Roblot, Counting primes in residue classes, Math. Comp. 73 (2004), no. 247, 1565–1575. MR 2047102, DOI 10.1090/S0025-5718-04-01649-7
- J.-M. Deshouillers, G. Effinger, H. te Riele, and D. Zinoviev, A complete Vinogradov $3$-primes theorem under the Riemann hypothesis, Electron. Res. Announc. Amer. Math. Soc. 3 (1997), 99–104. MR 1469323, DOI 10.1090/S1079-6762-97-00031-0
- J.-M. Deshouillers, H. J. J. te Riele, and Y. Saouter, New experimental results concerning the Goldbach conjecture, Algorithmic Number Theory: ANTS-III Proceedings (J. P. Buhler, ed.), Lecture Notes in Computer Science, vol. 1423, Springer-Verlag, Berlin / New York, 1998, pp. 204–215.
- Jean-Marc Deshouillers and Herman te Riele, On the probabilistic complexity of numerically checking the binary Goldbach conjecture in certain intervals, Number Theory and Its Applications (S. Kanemitsu and K. Gÿory, eds.), Kluwer Academic Publishers, Dordrecht / Boston / London, 1999, pp. 89–99.
- Leonard Eugene Dickson, History of the theory of numbers, vol. I: Divisibility and Primality, AMS Chelsea Publishing, Providence, Rhode Island, USA, 1992, Published originally by the Carnegie Institute of Washington (publication number 256) in 1919.
- Brian Dunten, Julie Jones, and Jonathan Sorenson, A space-efficient fast prime number sieve, Inform. Process. Lett. 59 (1996), no. 2, 79–84. MR 1409956, DOI 10.1016/0020-0190(96)00099-3
- W. Feller, The general form of the so-called law of the iterated logarithm, Trans. Amer. Math. Soc. 54 (1943), 373–402. MR 9263, DOI 10.1090/S0002-9947-1943-0009263-7
- P. X. Gallagher, On the distribution of primes in short intervals, Mathematika 23 (1976), no. 1, 4–9. MR 409385, DOI 10.1112/S0025579300016442
- William F. Galway, Dissecting a sieve to cut its need for space, Algorithmic number theory (Leiden, 2000) Lecture Notes in Comput. Sci., vol. 1838, Springer, Berlin, 2000, pp. 297–312. MR 1850613, DOI 10.1007/10722028_{1}7
- A. Granville, Harald Cramér and the distribution of prime numbers, Scandinavian Actuarial Journal 1995 (1995), no. 1, 12–28.
- A. Granville, J. van de Lune, and H. J. J. te Riele, Checking the Goldbach conjecture on a vector computer, Number Theory and Applications (R. A. Mollin, ed.), Kluwer Academic Publishers, Dordrecht / Boston / London, 1989, pp. 423–433.
- Richard K. Guy, Unsolved problems in number theory, 3rd ed., Problem Books in Mathematics, Springer-Verlag, New York, 2004. MR 2076335, DOI 10.1007/978-0-387-26677-0
- G. H. Hardy and J. E. Littlewood, Some problems of ‘partitio numerorum’; III: On the expression of a number as a sum of primes, Acta Mathematica 44 (1922), 1–70.
- G. H. Hardy and E. M. Wright, An introduction to the theory of numbers, 5th ed., The Clarendon Press, Oxford University Press, New York, 1979. MR 568909
- D. R. Heath-Brown, Gaps between primes, and the pair correlation of zeros of the zeta function, Acta Arith. 41 (1982), no. 1, 85–99. MR 667711, DOI 10.4064/aa-41-1-85-99
- Chen Jing-Run, On the representation of a large even number as the sum of a prime and the product of at most two primes, Sci. Sinica 21 (1978), 157–176, In chinese.
- Donald E. Knuth, 2006, PRIME-SIEVE-SPARSE program, retrieved on March 2012 from http://www-cs-faculty.stanford.edu/~uno/programs/prime-sieve-sparse.w.
- Emmanuel Kowalski, Averages of Euler products, distribution of singular series and the ubiquity of Poisson distribution, Acta Arith. 148 (2011), no. 2, 153–187. MR 2786162, DOI 10.4064/aa148-2-4
- J. C. Lagarias, V. S. Miller, and A. M. Odlyzko, Computing $\pi (x)$: the Meissel-Lehmer method, Math. Comp. 44 (1985), no. 170, 537–560. MR 777285, DOI 10.1090/S0025-5718-1985-0777285-5
- W. A. Light, J. Forrest, N. Hammond, and S. Roe, A note on Goldbach’s conjecture, BIT 20 (1980), no. 4, 525. MR 605912, DOI 10.1007/BF01933648
- Ming-Chit Liu and Tianze Wang, On the Vinogradov bound in the three primes Goldbach conjecture, Acta Arith. 105 (2002), no. 2, 133–175. MR 1932763, DOI 10.4064/aa105-2-3
- Wen Chao Lu, Exceptional set of Goldbach number, J. Number Theory 130 (2010), no. 10, 2359–2392. MR 2660899, DOI 10.1016/j.jnt.2010.03.017
- Thomas R. Nicely, New maximal prime gaps and first occurrences, Math. Comp. 68 (1999), no. 227, 1311–1315. MR 1627813, DOI 10.1090/S0025-5718-99-01065-0
- Bertil Nyman and Thomas R. Nicely, New prime gaps between $10^{15}$ and $5\times 10^{16}$, J. Integer Seq. 6 (2003), no. 3, Article 03.3.1, 6. MR 1997838
- Andrew Odlyzko, Michael Rubinstein, and Marek Wolf, Jumping champions, Experiment. Math. 8 (1999), no. 2, 107–118. MR 1700573, DOI 10.1080/10586458.1999.10504393
- Tomás Oliveira e Silva, Fast implementation of the segmented sieve of Eratosthenes, Available at http://www.ieeta.pt/~tos/software/prime_sieve.html\#n, August 2003, 2010.
- Tomás Oliveira e Silva, Computing $\pi (x)$: the combinatorial method, Revista do DETUA 4 (2006), no. 6, 759–768, Available at http://www.ieeta.pt/~tos/bib/5.4.html.
- Alphonse de Polignac, Six propositions arithmologiques déduites du cribe d’Eratosthène, Nouvelles Annales de Mathématiques 8 (1849), 423–429.
- Paul Pritchard, Explaining the wheel sieve, Acta Inform. 17 (1982), no. 4, 477–485. MR 685983, DOI 10.1007/BF00264164
- Paul Pritchard, Fast compact prime number sieves (among others), J. Algorithms 4 (1983), no. 4, 332–344. MR 729229, DOI 10.1016/0196-6774(83)90014-7
- Olivier Ramaré and Yannick Saouter, Short effective intervals containing primes, J. Number Theory 98 (2003), no. 1, 10–33. MR 1950435, DOI 10.1016/S0022-314X(02)00029-X
- Jörg Richstein, Verifying the Goldbach conjecture up to $4\cdot 10^{14}$, Math. Comp. 70 (2001), no. 236, 1745–1749. MR 1836932, DOI 10.1090/S0025-5718-00-01290-4
- Yannick Saouter, Checking the odd Goldbach conjecture up to $10^{20}$, Math. Comp. 67 (1998), no. 222, 863–866. MR 1451327, DOI 10.1090/S0025-5718-98-00928-4
- Pascal Sebah and Xavier Gourdon, Introduction to twin primes and Brun’s constant computation, Retrieved from http://numbers.computation.free.fr/Constants/Primes/twin.html on March 2012, 2002.
- Daniel Shanks, On maximal gaps between successive primes, Math. Comp. 18 (1964), 646–651. MR 167472, DOI 10.1090/S0025-5718-1964-0167472-8
- Mok-kong Shen, On checking the Goldbach conjecture, Nordisk Tidskr. Informationsbehandling (BIT) 4 (1964), 243–245. MR 172834, DOI 10.1007/bf01939515
- Richard C. Singleton, Algorithm $357$: An efficient prime number generator, Communications of the ACM 12 (1969), no. 10, 563–564.
- Matti K. Sinisalo, Checking the Goldbach conjecture up to $4\cdot 10^{11}$, Math. Comp. 61 (1993), no. 204, 931–934. MR 1185250, DOI 10.1090/S0025-5718-1993-1185250-6
- M. L. Stein and P. R. Stein, Experimental results on additive $2$-bases, Mathematics of Computation 19 (1965), no. 91, 427–434.
- Terence Tao, Every odd number greater than $1$ is the sum of at most five primes, Math. Comp., published electronically June 24, 2013.
- Marek Wolf, Some heuristics on the gaps between consecutive primes, arXiv:1102.0481v2 [math.NT], May 2011.
- Jeff Young and Aaron Potler, First occurrence prime gaps, Math. Comp. 52 (1989), no. 185, 221–224. MR 947470, DOI 10.1090/S0025-5718-1989-0947470-1
Bibliographic Information
- Tomás Oliveira e Silva
- Affiliation: Departamento de Electrónica, Telecomunicações e Informática / IEETA, Universidade de Aveiro, Portugal
- ORCID: 0000-0002-8878-3219
- Email: tos@ua.pt
- Siegfried Herzog
- Affiliation: Mont Alto Campus, The Pennsylvania State University, One Campus Drive, Mont Alto, Pennsylvania 17237
- Email: hgn@psu.edu
- Silvio Pardi
- Affiliation: INFN–Sezione di Napoli, Italy
- Email: spardi@na.infn.it
- Received by editor(s): May 21, 2012
- Received by editor(s) in revised form: December 6, 2012
- Published electronically: November 18, 2013
- © Copyright 2013 American Mathematical Society
- Journal: Math. Comp. 83 (2014), 2033-2060
- MSC (2010): Primary 11A41, 11P32, 11N35; Secondary 11N05, 11Y55
- DOI: https://doi.org/10.1090/S0025-5718-2013-02787-1
- MathSciNet review: 3194140