Sieving discussion thread

[R. Gerbicz]

Originally Posted by gribozavr

biwema, I'm intrested in this math, but I don't understand the "Newfactoring Depth ratio" part. Can you explain it to me, please? (I undersatnd that log2(x) is the number of bits in x)

I've figured out the correct calculation:
if you want an estimation for the number of survivors sieving by primes up to H and sieving k from Nmin to Nmax ( sieve only odd numbers ) then there will be about prodprime(p=3,H,(p-2)/p)*(Nmax-Nmin)/2 survivors because there are two forbidden resideu classes for every p>2 prime and primes are "independent".
So we need only to approximate prodprime(p=3,H,(p-2)/p).
Known limits:
limit(H->infinity,prodprime(p=3,H,p*(p-2)/(p-1)^2))=C2=0.6601618158 where C2 is the twin prime constant.
limit(H->infinity,prodprime(p=2,H,(p-1)/p)*log(H))=exp(-gamma) where gamma is the Euler-Mascheroni=0.5772156649. From these limits we can get:
limit(H->infinity,prodprime(p=3,H,(p-2)/p)*log(H)^2)=4*exp(-2*gamma)*C2.

So a good approximation for the number of survivors:
2*exp(-2*gamma)*C2*(Nmax-Nmin)/log(H)^(-2), here log is the natural logarithm.
Using your latest data: Nmax=25e9 and Nmin=400e6 and H=101.1T, so the estimation:
2*exp(-2*0.5772156649)*0.6601618158*(25*10^9-4*10^8)*log(101.1*10^12)^-2=9846234
Very good prediction because your correct data was 9849791

[biwema]

Originally Posted by gribozavr

biwema, I'm intrested in this math, but I don't understand the "Newfactoring Depth ratio" part. Can you explain it to me, please? (I undersatnd that log2(x) is the number of bits in x)

My mathematics behind is not that difficult:
The probability of not finding a factor of a number is

log(beginningfactorrange)/log(endfactorrange)

That is independant of the logarithm base (if you take the same base in the nominator and denominator.

I squared this number bevcause we are searching for twins (after sieving to 10^12 they are independant enough).

If you multiply it with the number of candidates, you get the remaining number of candidates.

the (24.7G / 24.8G) is just the proportional shotening if the range.

My predictions just say, that there are many too few candidates removed between 30.6T and 51.7T. Maybe your information was rounded or your initial data is taken from a range starting at 250M instead of 200M.

---
You can see that I'm a typical engineer (as you know it from many jokes):
Take some input (your statistical data on sieving) and predict the future with as few mathematics as possible.

R. Gerbicz is a typical mathematician: Take the whole equation with all constants etc.
It is amazing how accurate these numbers are (if you consider that the impact of the statistical variation is bigger at the beginning of sieving)

[gribozavr]

An Athlon64 machine sieved 150T-200T in parallel with Celeron sieving 100-150T.

Range [550e6; 25e9] at p=150.1T had 9,553,770 k's left.
Now the range [550e6; 25e9] is at p=215.6T, 9,345,423 k's left.

[gribozavr]

The range [550e6; 25e9] is at p=271.1T, 9,216,786 k's left.

[gribozavr]

Again, I sieved in parallel:

Range [550e6; 25e9] at p=300.0T had 9,160,689 k's left.
Now the range [550e6; 25e9] is at p=352.4T, 9,073,142 k's left.

[gribozavr]

I've got my hands on an Athlon XP 2500+ @1800Mhz and got a sieving rate of 9-15 sec/k. LLR takes about 150-200 sec, deending on the CPU. Maybe we should postpone LLR and start distributed sieving? With a couple of Athlon boxes we could sieve to 1000T quite easily.

The data file is 170 Mb uncompressed, about 35-40 Mb compressed. I have hosting/bandwidth for it.

I wonder, is there some ready software, that would allow to report factors only without uploading the whole data file.

[gribozavr]

Range [600e6; 25e9] at p=400.4T had 8,985,536 k's left.
Now the range [600e6; 25e9] is at p=550.8T, 8,878,628 k's left.

[jasong]

Originally Posted by gribozavr

Range [600e6; 25e9] at p=400.4T had 8,985,536 k's left.
Now the range [600e6; 25e9] is at p=550.8T, 8,878,628 k's left.

Would it be beneficial for my 2.8GHz Pentium-D to do some sieving? I know Pentiums are significantly slower, but I thought the help would be appreciated anyway.

[jasong]

I was doing a little surfing and discovered the following theorem about twin primes:

Theorem: (Clement 1949)
The integers n, n+2, form a pair of twin primes if and only if

4[(n-1)!+1] = -n (mod n(n+2))

I don't pretend to understand the math, but wonder if this theorem could be used to help sieving?

Edit: if the "!" means factorial, then this formula will most definitely NOT help sieving, but just in case it means something different, I'll go ahead and post this.

Originally Posted by jasong

but just in case it means something different, I'll go ahead and post this.

nope, it is factorial

[jasong]

Theorem: (Clement 1949)
The integers n, n+2, form a pair of twin primes if and only if

4[(n-1)!+1] = -n (mod n(n+2))

I've been thinking about this, and I'd like to throw something out there again.

Would it be possible to find patterns in the (n-1)! part of the equation? Maybe a situation where the last 6 to some odd digits are calculated correctly?

Even a partial pattern might be helpful.

I know there are plenty of people out there who have better skills than I do!