mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Blogorrhea > MattcAnderson

Reply
 
Thread Tools
Old 2017-03-19, 18:23   #1
MattcAnderson
 
MattcAnderson's Avatar
 
"Matthew Anderson"
Dec 2010
Oregon, USA

62310 Posts
Wink 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
Attached Files
File Type: pdf another goldbach weak 2.pdf (118.7 KB, 102 views)
MattcAnderson is offline   Reply With Quote
Old 2017-03-19, 19:01   #2
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

26118 Posts
Default

Quote:
Originally Posted by MattcAnderson View Post
I wrote some Maple (Maple is a computer algebra system.) code in order to shine a light on Harald's accomplishment.
That is a surprisingly slow implementation.
R. Gerbicz is offline   Reply With Quote
Old 2017-03-19, 20:18   #3
MattcAnderson
 
MattcAnderson's Avatar
 
"Matthew Anderson"
Dec 2010
Oregon, USA

7·89 Posts
Default

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
Attached Files
File Type: pdf Goldbach weak 6_2.pdf (322.4 KB, 93 views)
MattcAnderson is offline   Reply With Quote
Old 2017-03-19, 22:24   #4
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

2×3×151 Posts
Default

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;'
Pari/GP has a similar forpart function which last I checked was better optimized for restrictions so might run even faster. I am drawing a blank on a simple shortcutting "all" vector predicate, but worst case you could use a verbose for loop like Luschny's code.

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.
danaj is offline   Reply With Quote
Old 2017-03-19, 22:36   #5
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

2×3×151 Posts
Default

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).
danaj is offline   Reply With Quote
Old 2017-03-20, 03:59   #6
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2·2,969 Posts
Default

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)))
It takes about 31 seconds to find the a(1000) = 2216 3-Goldbach partitions of 2001.

Code:
gold1(n)=my(s,t); forprime(p=(n+2)\3,n-6, t=n-p; forprime(q=t\2,min(t-3,p), if(isprime(t-q), s++))); s
82 milliseconds for a(7000) = 48363 3-Goldbach partitions of 14001, about 2 milliseconds for a(1000). a(10^4) = 87357 took 166 ms, a(10^5) = 4242960 took 11 seconds.

These should definitely be improvable -- sieving should replace the final primality test for fairly large gains. But not bad for a one-line script.
CRGreathouse is offline   Reply With Quote
Old 2017-03-20, 04:18   #7
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

134628 Posts
Default

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 2017-03-20 at 04:20
CRGreathouse is offline   Reply With Quote
Old 2017-03-20, 04:19   #8
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

2×3×151 Posts
Default

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 co-authored 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.
danaj is offline   Reply With Quote
Old 2017-03-20, 04:35   #9
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2·2,969 Posts
Default

Quote:
Originally Posted by danaj View Post
The OEIS sequence was fun, but to be clear it is horrifically slow in terms of the simpler question for the ternary Goldbach conjecture.
Definitely -- any time you have a sequence that counts things, and a conjecture that says that from some point on, a(n) > 0, it's a waste to construct all of the things when you could just find one and then move on, and that goes double for sequences like this with near-quadratic (assumed) growth.

Quote:
Originally Posted by danaj View Post
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 co-authored with Platt points out how useful that result was. He notes it took 25 hours on a single core to finish the verification.
Yep. Although since they ended up going 8875 times higher the final calculation took 40,000 CPU-hours. Hmm, that's actually pretty good -- only 1600 times longer, they must have improved the algorithm further between those two.
CRGreathouse is offline   Reply With Quote
Old 2017-03-20, 05:37   #10
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

16128 Posts
Default

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 double-forprime 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 2017-03-20 at 05:39
danaj is offline   Reply With Quote
Old 2017-03-20, 15:02   #11
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2×2,969 Posts
Default

Quote:
Originally Posted by danaj View Post
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).
I also thought Appendix C looked interesting. I liked the pick-and-choose results.
CRGreathouse is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Factorial and Goldbach conjecture. MisterBitcoin MisterBitcoin 17 2018-01-29 00:50
Goldbach's weak conjecture MattcAnderson MattcAnderson 1 2017-03-18 23:32
Goldbach Conjecture MattcAnderson MattcAnderson 3 2017-03-17 15:34
Goldbach's Conjecture Patrick123 Miscellaneous Math 242 2011-03-15 14:28
Goldbach's conjecture Citrix Puzzles 3 2005-09-09 13:58

All times are UTC. The time now is 11:40.

Sat Nov 28 11:40:47 UTC 2020 up 79 days, 8:51, 3 users, load averages: 0.92, 1.09, 1.17

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.