How do you efficiently sieve for prime 3/4-tuples?

[henryzz]

Originally Posted by henryzz

Quite possibly.
I am going to attempt running it with gprof. Win64 with gpof support isn't supported by fpc so trying linux.
Unfortunately my ubuntu virtual machine is 9.04 and can't upgrade easily. Downloading the 12.04 Beta 2 iso now.

Almost all of the time was spent in PROGRAM_DO_SIEVE_ITER

I will try the c code now.

[henryzz]

The c program is incredibly fast compared with the pacsal. It does use more memory but that should be livable with.

I just sieved 0-100T for 7-tuples upto 2G in about 4 hours. This used about 4Gb of memory but the testing was done in <5 minutes so I don't need to sieve so far. I am not sure the numbers in post #38 are correct. I searched ~1/7 of the range and the best I found was a 4-tuple. I will do 100T-200T this evening. Not decided what sieve bound I will use but much smaller.

edit: How much speed am I losing by doing two 100T chunks rather than one 200T?

[R. Gerbicz]

Originally Posted by henryzz

The c program is incredibly fast compared with the pacsal. It does use more memory but that should be livable with.

I just sieved 0-100T for 7-tuples upto 2G in about 4 hours. This used about 4Gb of memory but the testing was done in <5 minutes so I don't need to sieve so far. I am not sure the numbers in post #38 are correct. I searched ~1/7 of the range and the best I found was a 4-tuple. I will do 100T-200T this evening. Not decided what sieve bound I will use but much smaller.

edit: How much speed am I losing by doing two 100T chunks rather than one 200T?

That depends on all 4 parameters that you can give after #define. It is easier to wait for the first progress message, and from it get an estimation for the time. Note that running 0-100T takes the same time that running 100T-200T, so it doesn't depend on the starting value.

For 7 tuple biwema said that "Range per one tuple: 730000 T" at 301 digits (though not checked that these times are correct or not). So you searched 1/7000 of that range.

[henryzz]

Originally Posted by R. Gerbicz

For 7 tuple biwema said that "Range per one tuple: 730000 T" at 301 digits (though not checked that these times are correct or not). So you searched 1/7000 of that range.

That explains things. I will try a 200T search range tomorrow.

[henryzz]

Running 100T-200T upto 0.5G took 5/6 the time of upto 2G for 0T-100T and used only half the memory(2GB). The sieve file is 1.6x the size but testing is super quick at this size.
I found one more quad in 100T-200T

[firejuggler]

so... testing k 5-20 T for n=10011 have given me 2 3-tuple so far
5364983132499*2^10011+1
5364983132499*2^10011-1
- Twin -
5364983132499*2^10011+5
- 3-Tuple -

and

14575260764109*2^10011+1
14575260764109*2^10011-1
- Twin -
14575260764109*2^10011+5
- 3-Tuple -

I hope I will get at least 2 more

[biwema]

Originally Posted by firejuggler

so... testing k 5-20 T for n=10011 have given me 2 3-tuple so far

I hope I will get at least 2 more

How far did you sieve? How many primes / twins did you get?
On average you might expect 3 3-tuple per 10 T range.

Im am sorry that i did not yet answer about my calculations. I just was busy. I try to do my best and give a detailed answer this weekend.

[firejuggler]

32 M value sieved to 1G (with the quad sieve in this thread) to start, split in two, one half sieved to 125B o( 7220422 tested value) and 800B for the second half( 3M700k value left)
In the first half , 284 twin 1 truple. i havent finished testing the second half

[henryzz]

I am currently running 4 different versions of gsieve on a quad in parallel to test what sieve depth is best for 7-tuples. I am running 250M, 125M, 50M, and 10M.
At half way through 10M has about twice as many candidates as 50M but as testing is so fast(0.0014 per test) at n=1000 so there is still a saving. 125M isn't too far behind but 250M hasn't even reached half way yet(the other 3 have reached 3/4 as I type).
10M should complete in about 80 minutes. This is down from 4 hours it took to got to 2G.
Next I will fiddle with bound_small_primes.

[henryzz]

I spoke too soon saying 80 minutes was good. Increasing bound_small_primes to 13 took 35 minutes to complete and 17 took 22. 19 looks like it will take about 30.
I don't think there are any huge improvments left but I will fiddle with sieve_len and hash_bits.

[Puzzle-Peter]

Originally Posted by henryzz

I spoke too soon saying 80 minutes was good. Increasing bound_small_primes to 13 took 35 minutes to complete and 17 took 22. 19 looks like it will take about 30.
I don't think there are any huge improvments left but I will fiddle with sieve_len and hash_bits.

This is very interesting.

If I understood Robert correctly, you need a very large search range for bound_small_primes=19 to be efficient.

I'm really curious what sieve_len will do to performance and memory usage.