mersenneforum.org Sieving discussion thread
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

2006-06-24, 21:39   #23
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

2·3·233 Posts

Quote:
 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

2006-06-25, 22:22   #24
biwema

Mar 2004

17D16 Posts

Quote:
 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)

 2006-07-19, 19:18 #25 gribozavr     Mar 2005 Internet; Ukraine, Kiev 1100101112 Posts 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.
 2006-08-06, 11:48 #26 gribozavr     Mar 2005 Internet; Ukraine, Kiev 11·37 Posts The range [550e6; 25e9] is at p=271.1T, 9,216,786 k's left.
 2006-08-20, 17:56 #27 gribozavr     Mar 2005 Internet; Ukraine, Kiev 11×37 Posts 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.
 2006-08-27, 11:56 #28 gribozavr     Mar 2005 Internet; Ukraine, Kiev 19716 Posts 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.
 2006-09-14, 05:04 #29 gribozavr     Mar 2005 Internet; Ukraine, Kiev 11·37 Posts 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.
2006-10-12, 23:13   #30
jasong

"Jason Goatcher"
Mar 2005

1101101100012 Posts

Quote:
 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.

2006-10-22, 00:34   #31
jasong

"Jason Goatcher"
Mar 2005

5×701 Posts

I was doing a little surfing and discovered the following theorem about twin primes:
Quote:
 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.

Last fiddled with by jasong on 2006-10-22 at 00:37

2006-10-22, 02:26   #32
thommy

3×37×53 Posts

Quote:
 Originally Posted by jasong but just in case it means something different, I'll go ahead and post this.
nope, it is factorial

2006-10-22, 19:37   #33
jasong

"Jason Goatcher"
Mar 2005

5·701 Posts

Quote:
 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!

 Similar Threads Thread Thread Starter Forum Replies Last Post Lennart Conjectures 'R Us 31 2014-09-14 15:14 philmoore Five or Bust - The Dual Sierpinski Problem 66 2010-02-10 14:34 ltd Prime Sierpinski Project 76 2008-07-25 11:44 ltd Prime Sierpinski Project 26 2005-11-01 07:45 R.D. Silverman Factoring 7 2005-09-30 12:57

All times are UTC. The time now is 08:07.

Tue Sep 29 08:07:17 UTC 2020 up 19 days, 5:18, 0 users, load averages: 1.44, 1.71, 1.70