Sieving discussion thread

[jmblazek]

Originally Posted by CedricVonck

I have small question: if I want to hunt for a TWIP myself what type do I choose in NewPGen?

- Twin?
- SG
- CC
- BiTwin
- Twin/SG
- Twin/CC

base=2
n=450000
kmin=2
kmax=100.000.000.000

Select Twin...and yes, your input is correct.

You are searching for a twin in the form of k*2^450000+-1. You are searching through a k range of 0G to 100G.

Good Luck!

[ValerieVonck]

Thank you!

I am trying to mirroring the ranges from Twips, is my range setting ok?
Or is it OTT?

Ok I will sieve this range!

Regards
C.

[Cybertronic]

We have now 35832536 k's left (without range 400-500,550-700), 80000 new candidates are removed.
My calculation give me: 30000000 k's left with sieving up to 10000T.
Thats 300 candidates. per 1M.
New possible master file zipped (not uploaded): 54.7 MB

[MooMoo2]

Originally Posted by CedricVonck

Thank you!

I am trying to mirroring the ranges from Twips, is my range setting ok?
Or is it OTT?

Ok I will sieve this range!

Regards
C.

TPS has a >90% chance of finding a twin in the range 1-100G for n=333,333. If you also want a >90% chance of finding a twin for your exponent (450,000), you would want to sieve a range from 1-170G.

[ValerieVonck]

Ok thank you, I will do this!
I checked the option: "Include even values of k"

[MooMoo2]

Originally Posted by CedricVonck

Ok thank you, I will do this!
I checked the option: "Include even values of k"

In that case, you'll only need to sieve from 1-85G to have an >90% chance of finding a twin. This is because TPS doesn't include even k values.

[ValerieVonck]

Ok thx for the support!

[pacionet]

n=500,000
range: 0-50G
sieving depth: 11.6 T
candidates remaining: 23,000,000
rate: 1 k every 0.1 seconds

[pacionet]

Originally Posted by MooooMoo

P.S. A random rant
I just read a comment in there that states "avoidance of silly MooMoo names." Hmmm. Oh well, I'm still keeping it the same

And my Barney avatar isn't coming off either

[ValerieVonck]

Ok I have sieved to 42G.
It generated a 1.5GB file. (it contains 81M) candidates)
I have neither the ram to sieve this entire range at once.
I am thinking about splitting this monster in chunks of 1M-?M lines.
For the first 1M used head.exe, similar program as on unix.

But how can I "split" this monster file in smaller chunks?
Remember I am using Windows.

Thank you

[biwema]

Hi

The last few weeks the project TPS was critisized because we are not searching for bitwins, lucky plus / minus or Cunningham constellations.

I also feel a little bit guilty regarding that because I started the sieving of 333333.
To be honest, before sieving I also considered that option. I always liked to play with optimizations (for example sieving for twins when searching proth primes). The reason, why I didn’t sieve for larger constellation is the architecture and efficiency of NewPGen. Some time ago I was searching for the largest triplet where I didn’t sieve primorials but proths. Even there, where the exponents were much smaller, I needed huge arrays for sieving.

While twin with 500000 needs 230G to get a 90% chance, a constellation of 3 primes needs 10000G and a constellation of 4 primes needs 500000G (When sieving to 100P). While NewPGen can hold a range of 8 G in memory, you need to sieve 62000 pieces for the first few primes. That takes a lot of time.

Note: The deeper you sieve, the smaller gets the chance of finding a twin in a given range.

NewPGen:
During the fist stage of sieving, when k is still small, a bitmap is used. The maximum allocatable Memory is 485M; so at most 4 billion k or a range of 8G fit into one bitmap.
Therefore the range is splitted up and connected together after k=1G.
Afetr 1 G the number of candidates dropped from 4billion k to 450000 (constellation of 3) or 17000 (constellation of 4).
In that stage, NewPGen is not really optimal: It should merge the file, when the number of remaining candidates dropped to 1-10M. If it waits longer, the sieving per removed k gets slower.
After that, one should group the ranges into pieces of 100million remaining candidates and sieving until for example 75million candidates are left, then it makes sense to remerge them, that the entire range is splitted into as few pieces as possible.

Note: The efficiency of the sieve is proportional to the number of candidates in the array.

After reaching 1T, this will not happen too often anymore, but when k is small, it has a big influence on the sieving speed.

Besides that, sieving small primes like 3, 5, 7, 11 takes a lot of time. Here a presieved bitmap of a primordial size, could improve that stage. Sieving larger primes like 23, 29, 31 etc could also improves if not every removed candidate is counted but the whole bitmap is boolean AND with an pattern of size 23, 29, 31 etc Bytes.
At prime 1000 it is early enough to count the primes and new removed k.

My suggestion: It makes no sense to sieve other constellations than twin. We can do that later after a more specialized sieving software for the first part (k smaller than some T)

biwema