Goldbach's Conjecture: Hunting Counterexamples

[Aillas]

Maybe you already know about these 2 projects:

Primaboinca that search for counterexample to some conjectures (Agrawal's Conjecture & Popovych's conjecture). I'm not a mathematician, but it seems that talk about Golbach conjecture too.

Once upon a time, a boinc project project was setup for Goldbach conjecture here. But it seems the project is down now.

[bsquared]

Originally Posted by bsquared

I just tested up to 2^32 in about 8 minutes using the above routine.

I had some spare time last night and spent it re-doing this code. Using sieve-like techniques and representing even numbers in a compact bit array, I can now test up to 2^32 in about 20 seconds (~ 30x speed improvement over this original attempt). My prime finder doesn't scale as well though, so in the region of 10^18 my new code is still about 5 times slower than Tomas's...

[/useless_info]

[CRGreathouse]

Originally Posted by bsquared

I had some spare time last night and spent it re-doing this code. Using sieve-like techniques and representing even numbers in a compact bit array, I can now test up to 2^32 in about 20 seconds (~ 30x speed improvement over this original attempt). My prime finder doesn't scale as well though, so in the region of 10^18 my new code is still about 5 times slower than Tomas's...

[/useless_info]

Goes to show how good TOeS is, if a 30-fold improvement over a not-entirely-naive solution is still 5 times slower than his version...

[science_man_88]

Originally Posted by CRGreathouse

Goes to show how good TOeS is, if a 30-fold improvement over a not-entirely-naive solution is still 5 times slower than his version...

has anyone tried predicting the probability of it being true ?

x/(x/(log(x)-1)) = how many groups of the size of the primes their should be up to x

floor(x/2) = ? how many representations of x with 2 numbers there are.

the hard part I have is remembering the equations needed and predicting without mass generalization ( because the numbers in the representations are of vastly different sizes at times), the numbers we can expect according to it.

[CRGreathouse]

Originally Posted by science_man_88

has anyone tried predicting the probability of it being true ?

100%, rounded to a thousand decimal places.

It seems doubtful that you could find any number beyond the range that has already been checked which has fewer than a trillion representations.

[science_man_88]

Originally Posted by CRGreathouse

100%, rounded to a thousand decimal places.

fine don't care.

[bsquared]

Originally Posted by CRGreathouse

Goes to show how good TOeS is, if a 30-fold improvement over a not-entirely-naive solution is still 5 times slower than his version...

Yes, my thoughts exactly

My code still has some obvious inefficiencies that I haven't fixed because it would be a fair amount of work, so I think I could eventually have something equivalent to his. I'm not sure it would be worth while though... it would basically be an independent double-check.

Something to put on the shelf for another day.

[Christenson]

Originally Posted by bsquared

I had some spare time last night and spent it re-doing this code. Using sieve-like techniques and representing even numbers in a compact bit array, I can now test up to 2^32 in about 20 seconds (~ 30x speed improvement over this original attempt). My prime finder doesn't scale as well though, so in the region of 10^18 my new code is still about 5 times slower than Tomas's...

[/useless_info]

Let's talk about that sieve-like technique for a moment...I think I can get you at least part of the required speedup.

Suppose we want to hunt counterexamples near 2^64 in a tractable block of size B, say, 2^20, starting at L, for large number. Now, the high density of solutions says that a small block of primes just below L (maybe just 300 of them) can be combined with the primes from 3 to B+small to show that all the even numbers in B indeed do not have the property of being counterexamples. When we are done with the first block, the next block can be handled the same way, but a few more primes below L will be required since we are now starting with primes of size 2^20 instead of size 2 for the one addend. (Alternatively, the BEST primes to add would be those just below L+B, but you still don't need very many of them).

So the claim is, you can have a sparse knowledge of the primes in or near the block of numbers your are trying to exhaust of counterexamples, and still eliminate all the non-counterexamples. This saves on finding the large prime numbers at the expense of a bit more searching among somewhat larger addends.

Another approach might be to keep track of the "Q", or quality of your sieving amongst counterexample candidates. When it gets relatively poor, (measured by the number of candidates removed), it's time to look at the candidates one by one, rather than as sieve elements.

[bsquared]

Originally Posted by Christenson

Let's talk about that sieve-like technique for a moment...I think I can get you at least part of the required speedup.

Suppose we want to hunt counterexamples near 2^64 in a tractable block of size B, say, 2^20, starting at L, for large number. Now, the high density of solutions says that a small block of primes just below L (maybe just 300 of them) can be combined with the primes from 3 to B+small to show that all the even numbers in B indeed do not have the property of being counterexamples. When we are done with the first block, the next block can be handled the same way, but a few more primes below L will be required since we are now starting with primes of size 2^20 instead of size 2 for the one addend. (Alternatively, the BEST primes to add would be those just below L+B, but you still don't need very many of them).

So the claim is, you can have a sparse knowledge of the primes in or near the block of numbers your are trying to exhaust of counterexamples, and still eliminate all the non-counterexamples. This saves on finding the large prime numbers at the expense of a bit more searching among somewhat larger addends.

Another approach might be to keep track of the "Q", or quality of your sieving amongst counterexample candidates. When it gets relatively poor, (measured by the number of candidates removed), it's time to look at the candidates one by one, rather than as sieve elements.

Sounds interesting, and is in some respects the reverse of what I'm currently doing. My technique involves finding all primes in a largish block B (2^30) at the offset of interest (i.e., near 10^18) and then adding the smallest primes to all of these while packing the results in a bit array.

Here is the sieve (snippet):

// start at the beginning of the candidate range

uint64 mask_3_127 = 0x40b6894d325a65b7; 
uint64 mask_131_257 = 0x90CB4108C3252619;
uint64 mask_263_383 = 0x5244B0902D021A64;
uint64 mask_389_509 = 0x2514416894C308A2;

range = 1000000000;
rl = 1000000000000000000ULL;
ru = 1000000000000000000ULL + range;

i = 1;
while (PRIMES[i] < rl)
	i++;
			
while (PRIMES[i] < ru)
{
	int bit_offset = ((PRIMES[i] - rl + 3) >> 1) & 63;
	int word_num = ((PRIMES[i] - rl + 3) >> 1) >> 6;

	uint64 lm = mask_3_127 << bit_offset;
	uint64 hm = mask_3_127 >> (64 - bit_offset);

	cflags64[word_num] |= lm;
	cflags64[word_num+1] |= hm;

	lm = mask_131_257 << bit_offset;
	hm = mask_131_257 >> (64 - bit_offset);

	cflags64[word_num+1] |= lm;
	cflags64[word_num+2] |= hm;

	lm = mask_263_383 << bit_offset;
	hm = mask_263_383 >> (64 - bit_offset);

	cflags64[word_num+2] |= lm;
	cflags64[word_num+3] |= hm;

	lm = mask_389_509 << bit_offset;
	hm = mask_389_509 >> (64 - bit_offset);

	cflags64[word_num+3] |= lm;
	cflags64[word_num+4] |= hm;

	i++;
}

Each iteration, I add 95 different primes to each prime in the block B and simultaneously store all of the sums in a bit array (can you see how? ). This goes pretty fast (0.15 second to "sieve" a range of 1 billion integers at 10^18). Generating the primes in that range is the slow part, taking about 11 seconds. Testing all of the leftover even candidates that didn't get sieved (about a 1.6% survival rate) takes another second or so.

I think I can at least halve the prime generation part, which will get me pretty close to Tomas (I think, all I have to go on is one timing he gives in his webpage). I'd have to think more about your approach.