On the probabilistic complexity of numerically checking the binary Goldbach conjecture in certain intervals (Q2707584)

The Goldbach conjecture states that every even integer \(\geq 4\) can be written as a sum of two prime numbers. The authors and \textit{Y.~Saouter} [ANTS-III, Lect. Notes Comput. Sci. 1423, 204-215 (1998; Zbl 0957.11044)] have shown that the conjecture is true up to \(10^{14}\), and also for even numbers in the intervals \([10^{5i},10^{5i} +10^8]\), for \(i=3,4, \dots,20\) and \([10^{10i}, 10^{10i}+ 10^9]\), for \(i=20,21,\dots,30\).NEWLINENEWLINENEWLINEThe aim of the present paper is to give a heuristic analysis of the complexity of the algorithm they used in their computation. The analysis is based on a probabilistic model for the distribution of primes and leads to an expected complexity which is described in detail. A comparison of the heuristics and the observed data is also presented. The experimental results are in good agreement with the prediction, adding credence to the truth of the Goldbach conjecture.NEWLINENEWLINEFor the entire collection see [Zbl 0932.00040].