login
From Goldbach conjecture: number of decompositions of 2n into an unordered sum of two odd primes.
(Formerly M0104 N0040)
172

%I M0104 N0040 #166 Oct 28 2023 11:50:03

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

%T 5,6,5,5,7,4,5,8,5,4,9,4,5,7,3,6,8,5,6,8,6,7,10,6,6,12,4,5,10,3,7,9,6,

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

%N From Goldbach conjecture: number of decompositions of 2n into an unordered sum of two odd primes.

%C A weaker form of this conjecture, the ternary form, was proved by Helfgott (see link below). - _T. D. Noe_, May 14 2013

%C The Goldbach conjecture is that for n >= 3, this sequence is always positive.

%C This has been checked up to at least 10^18 (see A002372).

%C With the exception of the n=2 term, identical to A045917.

%C The conjecture has been verified up to 3 * 10^17 (see MathWorld link). - _Dmitry Kamenetsky_, Oct 17 2008

%C Languasco and Zaccagnini proved that, where Lambda is the von Mangoldt function, and R(n) = Sum_{i + j = n} Lambda(i)*Lambda(j) is the counting function for the Goldbach numbers, and for N >= 2 and assume the Riemann hypothesis (RH) holds, then Sum_{n = 1..N} R(n) = (N^2)/2 - 2*Sum_{rho} ((N^(rho+1))/(rho*(rho+1))) + O(N * log^3 N).

%C If 2n is the sum of two distinct primes, then neither prime divides 2n. - _Christopher Heiling_, Feb 28 2017

%D Calvin C. Clawson, "Mathematical Mysteries, the beauty and magic of numbers," Perseus Books, Cambridge, MA, 1996, Chapter 12, Pages 236-257.

%D Apostolos K. Doxiadis, Uncle Petros and Goldbach's Conjecture, Bloomsbury Pub. PLC USA, 2000.

%D D. A. Grave, Traktat z Algebrichnogo Analizu (Monograph on Algebraic Analysis). Vol. 2, p. 19. Vidavnitstvo Akademiia Nauk, Kiev, 1938.

%D H. Halberstam and H. E. Richert, 1974, "Sieve methods", Academic press, London, New York, San Francisco.

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

%D N. V. Maslova, On the coincidence of Grünberg-Kegel graphs of a finite simple group and its proper subgroup, Proceedings of the Steklov Institute of Mathematics April 2015, Volume 288, Supplement 1, pp 129-141; Original Russian Text: Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2014, Vol. 20, No. 1.

%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).

%H H. J. Smith, <a href="/A002375/b002375.txt">Table of n, a(n) for n = 1..20000</a> (first 10000 terms from T. D. Noe)

%H J.-M. Deshouillers, H. J. J. te Riele and Y. Saouter, <a href="https://ir.cwi.nl/pub/1222">New Experimental Results Concerning the Goldbach Conjecture</a>, Modelling, Analysis and Simulation [MAS], R 9804, p.1-12, Technical report, 1998.

%H James A. Farrugia, <a href="https://digitalcommons.usu.edu/etd/7153">Brun's 1920 Theorem on Goldbach's Conjecture</a>, Master's Thesis, Utah State University, All Graduate Theses and Dissertations (2018). 7153.

%H H. A. Helfgott, <a href="http://arxiv.org/abs/1205.5252">Minor arcs for Goldbach's problem</a>, arXiv:1205.5252 [math.NT], 2012-2013.

%H H. A. Helfgott, <a href="http://arxiv.org/abs/1305.2897">Major arcs for Goldbach's theorem</a>, arXiv:1305.2897 [math.NT], 2013-2014.

%H H. A. Helfgott, <a href="http://arxiv.org/abs/1312.7748">The ternary Goldbach conjecture is true</a>, arxiv:1312.7748 [math.NT], 2013.

%H H. A. Helfgott, <a href="http://arxiv.org/abs/1404.2224">The ternary Goldbach problem</a>, arXiv:1404.2224 [math.NT], 2014.

%H M. Herkommer, <a href="http://www.herkommer.org/goldbach/goldbach.htm">Goldbach Conjecture Research</a>

%H A. V. Kumchev and D. I. Tolev, <a href="https://arxiv.org/abs/math/0412220">An invitation to additive number theory</a>, arXiv:math/0412220 [math.NT], 2004.

%H Alessandro Languasco and Alessandro Zaccagnini, <a href="https://doi.org/10.1090/S0002-9939-2011-10957-2">The number of Goldbach representations of an integer</a>, Proc. Amer. Math. Soc. 140 (2012), 795-804 (<a href="https://arxiv.org/abs/1011.3198">preliminary version</a>, arXiv:1011.3198 [math.NT], 2010).

%H Jörg Richstein, <a href="http://dx.doi.org/10.1090/S0025-5718-00-01290-4">Verifying the Goldbach conjecture up to 4 * 10^14</a>, Math. Comput., 70 (2001), 1745-1749.

%H Vladimir Shevelev, <a href="https://arxiv.org/abs/0901.3102">Binary additive problems: recursions for numbers of representations</a>, arXiv:0901.3102 [math.NT], 2009-2013.

%H Matti K. Sinisalo, <a href="http://dx.doi.org/10.1090/S0025-5718-1993-1185250-6">Checking the Goldbach conjecture up to 4*10^11</a>, Math. Comp. 61 (1993), pp. 931-934.

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

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Goldbach%27s_conjecture">Goldbach's conjecture</a>

%H G. Xiao, WIMS server, <a href="http://wims.unice.fr/~wims/en_tool~number~goldbach.en.html">Goldbach</a>

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

%F From Halberstam and Richert: a(n) < (8+0(1))*c(n)*n/log(n)^2 where c(n) = Product_{p > 2} (1-1/(p-1)^2)*Product_{p|n, p > 2} (p-1)/(p-2). It is conjectured that the factor 8 can be replaced by 2. Is a(n) > n/log(n)^2 for n large enough? - _Benoit Cloitre_, May 20 2002

%F a(n) = ceiling(A002372(n)/2). - _Emeric Deutsch_, Jul 14 2004

%F G.f.: Sum_{j>=2} Sum_{i=2..j} x^(p(i) + p(j)), where p(k) is the k-th prime. - _Emeric Deutsch_, Aug 27 2007

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

%F For n >= 2, a(n) = Sum_{3 <= p <= n, p is prime} A(2*n - p) - binomial(A(n), 2) - a(n-1) - a(n-2) - ... - a(1), where A(n) = A033270(n) (see Example 1 in link of V. Shevelev). - _Vladimir Shevelev_, Jul 08 2013

%e 2 and 4 are not the sum of 2 odd primes, so a(1) = a(2) = 0; 6 = 3 + 3 (one way, so a(3) = 1); 8 = 3 + 5 (so a(4) = 1); 10 = 3 + 7 = 5 + 5 (so a(5) = 2); etc.

%p A002375 := proc(n) local s, p; s := 0; p := 3; while p<2*n do s := s+x^p; p := nextprime(p) od; (coeff(s^2, x, 2*n)+coeff(s,x,n))/2 end; [seq(A002375(n), n=1..100)];

%p a:=proc(n) local c,k; c:=0: for k from 1 to floor((n-1)/2) do if isprime(2*k+1)=true and isprime(2*n-2*k-1)=true then c:=c+1 else c:=c fi od end: A:=[0,0,seq(a(n),n=3..98)]; # _Emeric Deutsch_, Aug 27 2007

%p g:=sum(sum(x^(ithprime(i)+ithprime(j)),i=2..j),j=2..50): seq(coeff(g,x,2*n), n =1..98); # _Emeric Deutsch_, Aug 27 2007

%t f[n_] := Length[ Select[2n - Prime[ Range[2, PrimePi[n]]], PrimeQ]]; Table[ f[n], {n, 100}] (* Paul Abbott, Jan 11 2005 *)

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

%t Table[Count[IntegerPartitions[2n,{2}],_?(AllTrue[#,PrimeQ]&&FreeQ[#,2]&)],{n,100}] (* The program uses the AllTrue function from Mathematica version 10 *) (* _Harvey P. Dale_, Mar 01 2018 *)

%t j[n_] := If[PrimeQ[2 n - 1], 2 n - 1, 0]; A085090 = Array[j, 98];

%t r[n_] := Table[A085090[[k]] + A085090[[n - k + 1]], {k, 1, n}];

%t countzeros[l_List] := Sum[KroneckerDelta[0, k], {k, l}];

%t Table[((x = n - 2 countzeros[A085090[[1 ;; n]]] + countzeros[r[n]]) +

%t KroneckerDelta[OddQ[x], True])/2, {n, 1, 98}] (* _Fred Daniel Kline_, Aug 30 2018 *)

%o (MuPAD) A002375 := proc(n) local s,p; begin s := 0; p := 3; repeat if isprime(2*n-p) then s := s+1 end_if; p := nextprime(p+2); until p>n end_repeat; s end_proc:

%o (PARI) A002375(n)=sum(i=2,primepi(n),isprime(2*n-prime(i))) /* ...i=1... gives A045917 */

%o (PARI) apply( {A002375(n,s=0,N=2*n)=forprime(p=n, N-3, isprime(N-p)&&s++);s}, [1..100]) \\ _M. F. Hasler_, Jan 03 2023

%o (Magma) A002375 := func<n|#[p:p in[3..n]|IsPrime(p)and IsPrime(2*n-p)]>; [A002375(n):n in[1..98]];

%o (Sage)

%o def A002375(n):

%o P = primes(3, n+1)

%o M = (2*n - p for p in P)

%o F = [k for k in M if is_prime(k)]

%o return len(F)

%o [A002375(n) for n in (1..98)] # _Peter Luschny_, May 19 2013

%o (Haskell)

%o a002375 n = sum $ map (a010051 . (2 * n -)) $ takeWhile (<= n) a065091_list

%o -- _Reinhard Zumkeller_, Sep 02 2013

%Y See also A061358. Cf. A002372 (ordered sums), A002373, A002374, A045917.

%Y A023036 is (essentially) the first appearance of n and A000954 is the last (assumed) appearance of n.

%Y Cf. A065091, A010051, A001031 (a weaker form of the conjecture).

%K nonn,easy,look,nice

%O 1,5

%A _N. J. A. Sloane_

%E Beginning corrected by _Paul Zimmermann_, Mar 15 1996

%E More terms from _James A. Sellers_

%E Edited by _Charles R Greathouse IV_, Apr 20 2010