Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Empirical verification of the even Goldbach conjecture and computation of prime gaps up to $ 4\cdot 10^{18}$


Authors: Tomás Oliveira e Silva, Siegfried Herzog and Silvio Pardi
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
Published electronically: November 18, 2013
MathSciNet review: 3194140
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] Ralph G. Archibald, Goldbach's theorem, Scripta Mathematica 3 (1935), 44-50, 153-161.
  • [2] A. O. L. Atkin and D. J. Bernstein, Prime sieves using binary quadratic forms, Math. Comp. 73 (2004), no. 246, 1023-1030 (electronic). MR 2031423 (2004i:11147), https://doi.org/10.1090/S0025-5718-03-01501-1
  • [3] 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 0447090 (56 #5405)
  • [4] Jan Bohman and Carl-Erik Fröberg, Numerical results on the Goldbach conjecture, Nordisk Tidskr. Informationsbehandling (BIT) 15 (1975), no. 3, 239-243. MR 0389814 (52 #10644)
  • [5] Richard P. Brent, The first occurrence of large gaps between successive primes, Math. Comp. 27 (1973), 959-963. MR 0330021 (48 #8360)
  • [6] Richard P. Brent, The distribution of small gaps between successive primes, Math. Comp. 28 (1974), 315-324. MR 0330017 (48 #8356)
  • [7] Harald Cramér, On the order of magnitude of the difference between consecutive prime numbers, Acta Arithmetica II (1937), 23-46.
  • [8] 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 (96d:11139), https://doi.org/10.1090/S0025-5718-96-00674-6
  • [9] Marc Deléglise, Pierre Dusart, and Xavier-François Roblot, Counting primes in residue classes, Math. Comp. 73 (2004), no. 247, 1565-1575 (electronic). MR 2047102 (2005a:11152), https://doi.org/10.1090/S0025-5718-04-01649-7
  • [10] 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 (98g:11112), https://doi.org/10.1090/S1079-6762-97-00031-0
  • [11] 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.
  • [12] 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.
  • [13] 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.
  • [14] 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 (97g:11141), https://doi.org/10.1016/0020-0190(96)00099-3
  • [15] W. Feller, The general form of the so-called law of the iterated logarithm, Trans. Amer. Math. Soc. 54 (1943), 373-402. MR 0009263 (5,125c)
  • [16] P. X. Gallagher, On the distribution of primes in short intervals, Mathematika 23 (1976), no. 1, 4-9. MR 0409385 (53 #13140)
  • [17] 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 (2002g:11176), https://doi.org/10.1007/10722028_17
  • [18] A. Granville, Harald Cramér and the distribution of prime numbers, Scandinavian Actuarial Journal 1995 (1995), no. 1, 12-28.
  • [19] 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.
  • [20] Richard K. Guy, Unsolved problems in number theory, 3rd ed., Problem Books in Mathematics, Springer-Verlag, New York, 2004. MR 2076335 (2005h:11003)
  • [21] 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.
  • [22] 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 (81i:10002)
  • [23] 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 (83m:10078)
  • [24] 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.
  • [25] 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.
  • [26] 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 (2012d:11199), https://doi.org/10.4064/aa148-2-4
  • [27] 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 (86h:11111), https://doi.org/10.2307/2007973
  • [28] W. A. Light, J. Forrest, N. Hammond, and S. Roe, A note on Goldbach's conjecture, BIT 20 (1980), no. 4, 525. MR 605912 (82h:10003), https://doi.org/10.1007/BF01933648
  • [29] 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 (2003i:11147), https://doi.org/10.4064/aa105-2-3
  • [30] Wen Chao Lu, Exceptional set of Goldbach number, J. Number Theory 130 (2010), no. 10, 2359-2392. MR 2660899 (2011f:11133), https://doi.org/10.1016/j.jnt.2010.03.017
  • [31] Thomas R. Nicely, New maximal prime gaps and first occurrences, Math. Comp. 68 (1999), no. 227, 1311-1315. MR 1627813 (99i:11004), https://doi.org/10.1090/S0025-5718-99-01065-0
  • [32] 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 pp. (electronic). MR 1997838 (2004e:11143)
  • [33] Andrew Odlyzko, Michael Rubinstein, and Marek Wolf, Jumping champions, Experiment. Math. 8 (1999), no. 2, 107-118. MR 1700573 (2000f:11164)
  • [34] 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.
  • [35] 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.
  • [36] Alphonse de Polignac, Six propositions arithmologiques déduites du cribe d'Eratosthène, Nouvelles Annales de Mathématiques 8 (1849), 423-429.
  • [37] Paul Pritchard, Explaining the wheel sieve, Acta Inform. 17 (1982), no. 4, 477-485. MR 685983 (84g:10015), https://doi.org/10.1007/BF00264164
  • [38] Paul Pritchard, Fast compact prime number sieves (among others), J. Algorithms 4 (1983), no. 4, 332-344. MR 729229 (85h:11080), https://doi.org/10.1016/0196-6774(83)90014-7
  • [39] Olivier Ramaré and Yannick Saouter, Short effective intervals containing primes, J. Number Theory 98 (2003), no. 1, 10-33. MR 1950435 (2004a:11095), https://doi.org/10.1016/S0022-314X(02)00029-X
  • [40] Jörg Richstein, Verifying the Goldbach conjecture up to $ 4\cdot 10^{14}$, Math. Comp. 70 (2001), no. 236, 1745-1749 (electronic). MR 1836932 (2002c:11131), https://doi.org/10.1090/S0025-5718-00-01290-4
  • [41] Yannick Saouter, Checking the odd Goldbach conjecture up to $ 10^{20}$, Math. Comp. 67 (1998), no. 222, 863-866. MR 1451327 (98g:11115), https://doi.org/10.1090/S0025-5718-98-00928-4
  • [42] 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.
  • [43] Daniel Shanks, On maximal gaps between successive primes, Math. Comp. 18 (1964), 646-651. MR 0167472 (29 #4745)
  • [44] Mok-kong Shen, On checking the Goldbach conjecture, Nordisk Tidskr. Informations-Behandling 4 (1964), 243-245. MR 0172834 (30 #3051)
  • [45] Richard C. Singleton, Algorithm $ 357$: An efficient prime number generator, Communications of the ACM 12 (1969), no. 10, 563-564.
  • [46] Matti K. Sinisalo, Checking the Goldbach conjecture up to $ 4\cdot 10^{11}$, Math. Comp. 61 (1993), no. 204, 931-934. MR 1185250 (94a:11157), https://doi.org/10.2307/2153264
  • [47] M. L. Stein and P. R. Stein, Experimental results on additive $ 2$-bases, Mathematics of Computation 19 (1965), no. 91, 427-434.
  • [48] Terence Tao, Every odd number greater than $ 1$ is the sum of at most five primes, Math. Comp., published electronically June 24, 2013.
  • [49] Marek Wolf, Some heuristics on the gaps between consecutive primes, arXiv:1102.0481v2 [math.NT], May 2011.
  • [50] Jeff Young and Aaron Potler, First occurrence prime gaps, Math. Comp. 52 (1989), no. 185, 221-224. MR 947470 (89f:11019), https://doi.org/10.2307/2008665

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 11A41, 11P32, 11N35, 11N05, 11Y55

Retrieve articles in all journals with MSC (2010): 11A41, 11P32, 11N35, 11N05, 11Y55


Additional Information

Tomás Oliveira e Silva
Affiliation: Departamento de Electrónica, Telecomunicações e Informática / IEETA, Universidade de Aveiro, Portugal
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

DOI: https://doi.org/10.1090/S0025-5718-2013-02787-1
Keywords: Goldbach conjecture, prime gaps, prime $k$-tuple conjecture
Received by editor(s): May 21, 2012
Received by editor(s) in revised form: December 6, 2012
Published electronically: November 18, 2013
Article copyright: © Copyright 2013 American Mathematical Society

American Mathematical Society