20170319, 18:23  #1 
"Matthew Anderson"
Dec 2010
Oregon, USA
623_{10} Posts 
Goldbach's weak conjecture
Hi Mersenneforum,
In 2013, Harald Helfgott proved Goldbach's weak conjecture. See  Wikipedia Article about Goldbach's weak conjecture I wrote some Maple (Maple is a computer algebra system.) code in order to shine a light on Harald's accomplishment. Regards, Matt 
20170319, 19:01  #2 
"Robert Gerbicz"
Oct 2005
Hungary
2611_{8} Posts 

20170319, 20:18  #3 
"Matthew Anderson"
Dec 2010
Oregon, USA
7·89 Posts 
Hi again Mersenneforum,
So I was unable to improve my computer code significantly. I found better code at Online Encyclopedia of Integer Sequences My code cannot calculate gwc(7000) in under 102 seconds. At least it produces correct results. (as far as I tested it.) Regards, Matt 
20170319, 22:24  #4 
"Dana Jacobsen"
Feb 2011
Bangkok, TH
2×3×151 Posts 
I added a simple Perl program based on Luschny's algorithm. It takes ~5 seconds on my laptop for a(7000).
Code:
perl E 'use ntheory ":all"; sub a007963 { my($n,$c)=(shift,0); forpart { $c++ if vecall { is_prime($_) } @_; } $n,{n=>3,amin=>3}; $c; } say "$_ ",a007963(2*$_+1) for 0..100;' For OEIS use it's almost getting to the point where it would be worthwhile to add a isprime option to forpart as seems to keep coming up as a restriction. It would make this function trivial. 
20170319, 22:36  #5 
"Dana Jacobsen"
Feb 2011
Bangkok, TH
2×3×151 Posts 
It was simple (5 lines) to add a prime restriction to my forpart, and it runs this function about 20x faster, since forpart's C code is doing all the work. 0.25s for a(7000).

20170320, 03:59  #6 
Aug 2006
2·2,969 Posts 
Here's a translation of the original program into GP:
Code:
gold(n)=sum(a=2,n\3,sum(b=2,a,sum(c=2,b,prime(a)+prime(b)+prime(c)==n))) Code:
gold1(n)=my(s,t); forprime(p=(n+2)\3,n6, t=np; forprime(q=t\2,min(t3,p), if(isprime(tq), s++))); s These should definitely be improvable  sieving should replace the final primality test for fairly large gains. But not bad for a oneline script. 
20170320, 04:18  #7 
Aug 2006
13462_{8} Posts 
13 minutes, 52 seconds to get a(10^6) = 235945824.
While I'm here I'll also advertise my post on the other Goldbach thread Matt started recently, where I attempt to summarize Helfgott's basic argument. Last fiddled with by CRGreathouse on 20170320 at 04:20 
20170320, 04:19  #8 
"Dana Jacobsen"
Feb 2011
Bangkok, TH
2×3×151 Posts 
The OEIS sequence was fun, but to be clear it is horrifically slow in terms of the simpler question for the ternary Goldbach conjecture.
Helfgott in his intro describes the covering for all n < 10^27 "really a minor computational task." 1.2.2 discusses some methods. Using Oliveira e Silva et al.'s results of the binary Goldbach conjecture to 4*10^18 make it quite reasonable  this rather underplays the considerable effort of that check. The paper coauthored with Platt points out how useful that result was. He notes it took 25 hours on a single core to finish the verification. I wrote a simple checker and it's quite fast at first. Helfgott and Platt use a method that saves time on the primality proof by spending more time on the selection. I just used a simple prec_prime + is_provable_prime loop. The precprimes themselves are less than 2 hours on a single core to reach 10^27. The proofs are very fast until 3*10^24, then start sucking up quite a bit of time. I'm not sure it'd beat 25 hours, but I don't think it'd be too far off. 
20170320, 04:35  #9  
Aug 2006
2·2,969 Posts 
Quote:
Quote:


20170320, 05:37  #10 
"Dana Jacobsen"
Feb 2011
Bangkok, TH
1612_{8} Posts 
Thanks for your posts, Charles. Reading your summary as well as skimming some of the papers including Helfgott's has made for an entertaining Sunday.
My (technically Luschny's) partition method for 10^5 takes about 70 seconds to get 4242960. Your simple Pari doubleforprime loop took 17 seconds. The same algorithm in Perl/ntheory took 3 seconds. A bit under 5 minutes for 10^6. I miss having a nice integer divide operator ('\'). I wish I had labeled forprimes variables. Re the CPU time, they note 40k CPU hours in parallel with some heterogeneous machines, and it looks like they took care to include some checks with different software, and went >7000x more than needed (8.875e30 vs. 1.23e27). Not sure why the difference  could be old vs. new software, could be being conservative with "modern processor", etc. It looks like Appendix C works it out in a different way, using numerical Riemann Zeta zero results (three different groups) and papers by Ramarè and Saouter. The latter are pretty interesting including some other groups extending these results (e.g. Kadiri and Lumley 2014). Last fiddled with by danaj on 20170320 at 05:39 
20170320, 15:02  #11  
Aug 2006
2×2,969 Posts 
Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Factorial and Goldbach conjecture.  MisterBitcoin  MisterBitcoin  17  20180129 00:50 
Goldbach's weak conjecture  MattcAnderson  MattcAnderson  1  20170318 23:32 
Goldbach Conjecture  MattcAnderson  MattcAnderson  3  20170317 15:34 
Goldbach's Conjecture  Patrick123  Miscellaneous Math  242  20110315 14:28 
Goldbach's conjecture  Citrix  Puzzles  3  20050909 13:58 