login
Goldbach conjecture: a(n) = number of decompositions of 2n into sum of two primes (counting 1 as a prime).
(Formerly M0213 N0077)
22

%I M0213 N0077 #67 Jun 04 2022 12:11:37

%S 1,2,2,2,2,2,3,2,3,3,3,4,3,2,4,3,4,4,3,3,5,4,4,6,4,3,6,3,4,7,4,5,6,3,

%T 5,7,6,5,7,5,5,9,5,4,10,4,5,7,4,6,9,6,6,9,7,7,11,6,6,12,4,5,10,4,7,10,

%U 6,5,9,8,8,11,6,5,13,5,8,11,6,8,10,6,6,14,9,6,12,7,7,15,7,8,13,5,8,12,8,9

%N Goldbach conjecture: a(n) = number of decompositions of 2n into sum of two primes (counting 1 as a prime).

%D T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, page 9.

%D Deshouillers, J.-M.; te Riele, H. J. J.; and Saouter, Y.; New experimental results concerning the Goldbach conjecture. Algorithmic number theory (Portland, OR, 1998), 204-215, Lecture Notes in Comput. Sci., 1423, Springer, Berlin, 1998.

%D Apostolos Doxiadis: Uncle Petros and Goldbach's Conjecture, Faber and Faber, 2001

%D R. K. Guy, Unsolved problems in number theory, second edition, Springer-Verlag, 1994.

%D D. H. Lehmer, Guide to Tables in the Theory of Numbers. Bulletin No. 105, National Research Council, Washington, DC, 1941, p. 79.

%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 M. L. Stein and P. R. Stein, Tables of the Number of Binary Decompositions of All Even Numbers Less Than 200,000 into Prime Numbers and Lucky Numbers. Report LA-3106, Los Alamos Scientific Laboratory of the University of California, Los Alamos, NM, Sep 1964.

%H T. D. Noe, <a href="/A001031/b001031.txt">Table of n, a(n) for n = 1..10000</a>

%H G. H. Hardy and J. E. Littlewood, <a href="https://doi.org/10.1007/BF02403921">Some problems of 'Partitio numerorum'; III: On the expression of a number as a sum of primes</a>, Acta Math., Vol. 44, No. 1 (1923), pp. 1-70.

%H Romeo Meštrović, <a href="https://arxiv.org/abs/1804.00992">Different classes of binary necklaces and a combinatorial method for their enumerations</a>, arXiv:1804.00992 [math.CO], 2018.

%H T. Oliveira e Silva, <a href="http://sweet.ua.pt/tos/goldbach.html">Goldbach conjecture verification</a>

%H J. Richstein, <a href="https://doi.org/10.1090/S0025-5718-00-01290-4">Verifying the Goldbach conjecture up to 4*10^14</a>, Mathematics of Computation, Vol. 70, No. 236, pp. 1745-1749, 2001.

%H Matti K. Sinisalo, <a href="https://doi.org/10.1090/S0025-5718-1993-1185250-6">Checking the Goldbach conjecture up to 4*10^11</a>, Mathematics of Computation, Vol. 61, No. 204, pp. 931-934, October 1993.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/GoldbachPartition.html">Goldbach Partition</a>

%H <a href="/index/Go#Goldbach">Index entries for sequences related to Goldbach conjecture</a>

%F Not very efficient: a(n) = (Sum_{i=1..n} (pi(i) - pi(i-1))*(pi(2*n-i) - pi(2*n-i-1))) + (pi(2*n-1) - pi(2*n-2)) + floor(1/n). - _Wesley Ivan Hurt_, Jan 06 2013

%F a(n) = floor((A096139(n)+1)/2). - _Reinhard Zumkeller_, Aug 28 2013

%e 1 is counted as a prime, so a(1)=1 since 2=1+1, a(2)=2 since 4=2+2=3+1, ..

%t nn = 10^2; ps = Boole[PrimeQ[Range[2*nn]]]; ps[[1]] = 1; Table[Sum[ps[[i]] ps[[2*n - i]], {i, n}], {n, nn}] (* _T. D. Noe_, Apr 11 2011 *)

%o (Haskell)

%o a001031 n = sum (map a010051 gs) + fromEnum (1 `elem` gs)

%o where gs = map (2 * n -) $ takeWhile (<= n) a008578_list

%o -- _Reinhard Zumkeller_, Aug 28 2013

%o (PARI) a(n)=my(s); forprime(p=2,n, if(isprime(2*n-p), s++)); if(isprime(2*n-1), s+1, s) \\ _Charles R Greathouse IV_, Feb 06 2017

%Y Cf. A002372 (the main entry), A002373, A002374, A002375, A006307, A008578, A010051, A045917.

%K nonn,easy,nice

%O 1,2

%A _N. J. A. Sloane_

%E More terms from _Ray Chandler_, Sep 19 2003