PrimeGrid
Please visit donation page to help the project cover running costs for this month

Toggle Menu

Join PrimeGrid

Returning Participants

Community

Leader Boards

Results

Other

drummers-lowrise

Advanced search

Message boards : Sieving : Numerical equation for GFN sieve speed at specific depth

Author Message
Profile MyrskylyhtyProject donor
Avatar
Send message
Joined: 27 Jan 18
Posts: 80
ID: 972376
Credit: 193,988,087
RAC: 1,428,602
321 LLR Sapphire: Earned 20,000,000 credits (20,060,555)Cullen LLR Gold: Earned 500,000 credits (533,200)ESP LLR Silver: Earned 100,000 credits (314,648)Generalized Cullen/Woodall LLR Bronze: Earned 10,000 credits (67,663)PPS LLR Gold: Earned 500,000 credits (897,985)PSP LLR Gold: Earned 500,000 credits (719,124)SoB LLR Silver: Earned 100,000 credits (485,642)SR5 LLR Amethyst: Earned 1,000,000 credits (1,003,678)SGS LLR Silver: Earned 100,000 credits (128,562)TRP LLR Silver: Earned 100,000 credits (297,460)Woodall LLR Silver: Earned 100,000 credits (380,849)Generalized Cullen/Woodall Sieve Amethyst: Earned 1,000,000 credits (1,064,320)PPS Sieve Emerald: Earned 50,000,000 credits (61,439,846)AP 26/27 Amethyst: Earned 1,000,000 credits (1,524,211)GFN Sapphire: Earned 20,000,000 credits (32,524,227)PSA Emerald: Earned 50,000,000 credits (72,546,119)
Message 120919 - Posted: 5 Oct 2018 | 7:32:42 UTC
Last modified: 5 Oct 2018 | 7:35:58 UTC

I had lots of fun procrastinating yesterday, since I decided to analyse the sieve statistics which are available on this page: http://www.primegrid.com/sieving/gfn/

Especially, I wanted to find out what is the "removed from sieve" rate at specific depths. This "removed from sieve" number tells how much candidates under 100M were removed at the sieved range (Under 400M for GFN15-GFN16). I focused on only on GFN17-GFN22

This is what we see when we plot the rates logarithmically:


X axis is the sieve depth (in P, Peta), and Y axis is the removed from sieve value.

You can immediately see that the rate seems to be a logartichmic power law, most clearly between 200P and 20000P. Under this the ranges are relatively large, causing a flat interval because we only get one value for the range sieved. After 20000P there are a lot of small ranges sieved combined with inaccuracy caused by the sieverate only showing the first decimal when going to smaller rates.

So, since the rates seem to be a straight line (i.e. a power law), we can fit a line through the values between 200P and 20000P. From this fit we get an equation for the sieverate for all the 6 project, which are as follows:

GFN17: 10^(5.699895611539641 - 1.047809735406364 * log10(P))
GFN18: 10^(5.770189918802291 - 1.047054122505504 * log10(P))
GFN19: 10^(5.773619230259421 - 1.047460916471634 * log10(P))
GFN20: 10^(5.822252032580029 - 1.048505447896963 * log10(P))
GFN21: 10^(5.857281943722451 - 1.045637924155947 * log10(P))
GFN22: 10^(5.893575606716400 - 1.046124290520683 * log10(P))

So, you can use these numerical equations to estimate the "removed from sieve" rates for a specific depth P.

Using the equation, we can predict the current rates of "removed from sieve", which are as follows (latest real rate of one large sieve interval in parentheses):

GFN17: 1.607641841985315 (1.6)
GFN18: 2.157718107008705 (2.2)
GFN19: 1.307389966120157 (1.3)
GFN20: 2.321153593850324 (2.4)
GFN21: 1.110968091110168 (1.2)
GFN22: 1.024786816287452 (1.0)

This result tells how many are removed from values under b<100M for each P (=Remove density). But if we assume that the removals are evenly distributed (which is roughly the case), you can just multiple the value by the fraction you are interested in. So if you would be interested in ranges 0-1M or 50M-51M, you would multiply this result by 0.01.

You can also predict how many removals sieving a specific range would net. Taking 150050P to 200200P of GFN19 as an example, the equation sums up to 96585 removals in this range. The real number of removals was 97266, so there was a 0.7% difference between the equation and the reality. Similarly we can predict that sieving GFN17 from 175000P to 200000P would net about 37449 removals.

This equation works quite well for approximating rates from 1P onwards, but it doesnt tell how much removals are done at the start of the sieve, since the equation doesnt work for values between 0 and 1P (log10(0)= -Infinity). But it does seem to work after the first sieve range in the stats:

GFN17 predicted removals between 75P to 175000P: 2644000
GFN17 real number of removals 75P to 175000P: 2635698 (actually there's a few ranges still sieving)

GFN20 predicted removals between 50P to 160000P: 3674325
GFN20 real number of removals 50P to 160000P: 3674668 (Thats only a 0,009% error)

I dunno if there already is a some analytical equation for the stuff I've calculated (maybe related to the value of π(x)/(x / log x)? See https://en.wikipedia.org/wiki/Prime_number_theorem ), but its always nice to have numerical verification :)

This method could also work for other types of sieve, if similar stats are available somewhere.

All feedback, corrections and ideas are very welcome :)

JimBProject donor
Volunteer moderator
Project administrator
Project developer
Send message
Joined: 4 Aug 11
Posts: 785
ID: 107307
Credit: 667,877,373
RAC: 341,552
321 LLR Ruby: Earned 2,000,000 credits (2,054,472)Cullen LLR Ruby: Earned 2,000,000 credits (2,500,846)ESP LLR Ruby: Earned 2,000,000 credits (3,823,612)Generalized Cullen/Woodall LLR Ruby: Earned 2,000,000 credits (2,157,923)PPS LLR Ruby: Earned 2,000,000 credits (2,100,471)PSP LLR Turquoise: Earned 5,000,000 credits (5,013,650)SoB LLR Sapphire: Earned 20,000,000 credits (24,453,382)SR5 LLR Jade: Earned 10,000,000 credits (10,153,648)SGS LLR Ruby: Earned 2,000,000 credits (2,000,775)TRP LLR Ruby: Earned 2,000,000 credits (2,105,945)Woodall LLR Ruby: Earned 2,000,000 credits (2,445,894)Cullen/Woodall Sieve (suspended) Ruby: Earned 2,000,000 credits (4,002,919)Generalized Cullen/Woodall Sieve Jade: Earned 10,000,000 credits (10,106,760)PPS Sieve Emerald: Earned 50,000,000 credits (50,809,179)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Ruby: Earned 2,000,000 credits (2,341,676)TRP Sieve (suspended) Ruby: Earned 2,000,000 credits (2,070,804)AP 26/27 Jade: Earned 10,000,000 credits (10,592,660)GFN Sapphire: Earned 20,000,000 credits (29,095,001)PSA Double Gold: Earned 500,000,000 credits (500,047,755)
Message 120920 - Posted: 5 Oct 2018 | 12:10:04 UTC - in response to Message 120919.

After 20000P there are a lot of small ranges sieved combined with inaccuracy caused by the sieverate only showing the first decimal when going to smaller rates.

You've got the exact size of the sieving range and the exact count of factors found and removed. I think you can figure out the rate yourself to as many digits as you'd like.

Profile MyrskylyhtyProject donor
Avatar
Send message
Joined: 27 Jan 18
Posts: 80
ID: 972376
Credit: 193,988,087
RAC: 1,428,602
321 LLR Sapphire: Earned 20,000,000 credits (20,060,555)Cullen LLR Gold: Earned 500,000 credits (533,200)ESP LLR Silver: Earned 100,000 credits (314,648)Generalized Cullen/Woodall LLR Bronze: Earned 10,000 credits (67,663)PPS LLR Gold: Earned 500,000 credits (897,985)PSP LLR Gold: Earned 500,000 credits (719,124)SoB LLR Silver: Earned 100,000 credits (485,642)SR5 LLR Amethyst: Earned 1,000,000 credits (1,003,678)SGS LLR Silver: Earned 100,000 credits (128,562)TRP LLR Silver: Earned 100,000 credits (297,460)Woodall LLR Silver: Earned 100,000 credits (380,849)Generalized Cullen/Woodall Sieve Amethyst: Earned 1,000,000 credits (1,064,320)PPS Sieve Emerald: Earned 50,000,000 credits (61,439,846)AP 26/27 Amethyst: Earned 1,000,000 credits (1,524,211)GFN Sapphire: Earned 20,000,000 credits (32,524,227)PSA Emerald: Earned 50,000,000 credits (72,546,119)
Message 120922 - Posted: 5 Oct 2018 | 12:47:49 UTC - in response to Message 120920.
Last modified: 5 Oct 2018 | 12:51:26 UTC

After 20000P there are a lot of small ranges sieved combined with inaccuracy caused by the sieverate only showing the first decimal when going to smaller rates.

You've got the exact size of the sieving range and the exact count of factors found and removed. I think you can figure out the rate yourself to as many digits as you'd like.


Actually I mispoke. I did not use "removed density" in any of my calculations, except when comparing to the equation. Just a brain fart on my part.

The real reason for the higher variance is most likely that when the sieverate goes down, the variance in small sieve ranges (only 1P for example) will be very large. Here's a prime example:


Here is also the image from the first post, since the link seems to have stopped working:

Yves Gallot
Volunteer developer
Send message
Joined: 19 Aug 12
Posts: 464
ID: 164101
Credit: 232,891,170
RAC: 565,363
GFN Double Silver: Earned 200,000,000 credits (232,891,170)
Message 120924 - Posted: 5 Oct 2018 | 15:22:43 UTC

You can find the formula for the expected number of candidates at:
http://www.primegrid.com/forum_thread.php?id=4417&nowrap=true#57237

We have #candidates = e^-gamma * C_n * B_max / log(p_max)
where
C_15 = 5.80266
C_16 = 11.1957
C_17 = 11.0043
C_18 = 13.0078
C_19 = 13.0724
C_20 = 14.5167
C_21 = 16.0846
C_22 = 17.4099

Profile MyrskylyhtyProject donor
Avatar
Send message
Joined: 27 Jan 18
Posts: 80
ID: 972376
Credit: 193,988,087
RAC: 1,428,602
321 LLR Sapphire: Earned 20,000,000 credits (20,060,555)Cullen LLR Gold: Earned 500,000 credits (533,200)ESP LLR Silver: Earned 100,000 credits (314,648)Generalized Cullen/Woodall LLR Bronze: Earned 10,000 credits (67,663)PPS LLR Gold: Earned 500,000 credits (897,985)PSP LLR Gold: Earned 500,000 credits (719,124)SoB LLR Silver: Earned 100,000 credits (485,642)SR5 LLR Amethyst: Earned 1,000,000 credits (1,003,678)SGS LLR Silver: Earned 100,000 credits (128,562)TRP LLR Silver: Earned 100,000 credits (297,460)Woodall LLR Silver: Earned 100,000 credits (380,849)Generalized Cullen/Woodall Sieve Amethyst: Earned 1,000,000 credits (1,064,320)PPS Sieve Emerald: Earned 50,000,000 credits (61,439,846)AP 26/27 Amethyst: Earned 1,000,000 credits (1,524,211)GFN Sapphire: Earned 20,000,000 credits (32,524,227)PSA Emerald: Earned 50,000,000 credits (72,546,119)
Message 120928 - Posted: 5 Oct 2018 | 20:34:26 UTC - in response to Message 120924.

You can find the formula for the expected number of candidates at:
http://www.primegrid.com/forum_thread.php?id=4417&nowrap=true#57237

We have #candidates = e^-gamma * C_n * B_max / log(p_max)
where
C_15 = 5.80266
C_16 = 11.1957
C_17 = 11.0043
C_18 = 13.0078
C_19 = 13.0724
C_20 = 14.5167
C_21 = 16.0846
C_22 = 17.4099


Ooh, nice.

So for C_20, B_max=1E8 and we obtain

#candidates = e^(-0.5772156649) * (14.5167*10^8) / log(p_max)
And in log10:
#candidates = 10^8.5490 /log10(p_max)

For GFN20 50P to 160000P this formula gives a difference of

10^8.5490 /log10(50*10^15)-10^8.5490 /log10(160000*10^15)

= 3677706

It is of course also possible obtain the sieverate from this or vice versa. Nice to see that my shenanigans are working.

PS: it seems my image links from dropbox keep dying...

Profile RobishProject donor
Avatar
Send message
Joined: 7 Jan 12
Posts: 489
ID: 126266
Credit: 1,704,639,333
RAC: 3,047,360
Discovered 7 mega primes2018 Tour de Primes largest primeFound 4 primes in the 2018 Tour de PrimesFound 1 mega prime in the 2018 Tour de Primes321 LLR Turquoise: Earned 5,000,000 credits (5,232,081)Cullen LLR Turquoise: Earned 5,000,000 credits (7,698,840)ESP LLR Ruby: Earned 2,000,000 credits (3,044,572)Generalized Cullen/Woodall LLR Turquoise: Earned 5,000,000 credits (5,101,605)PPS LLR Jade: Earned 10,000,000 credits (15,802,127)PSP LLR Ruby: Earned 2,000,000 credits (4,189,596)SoB LLR Sapphire: Earned 20,000,000 credits (26,691,213)SR5 LLR Turquoise: Earned 5,000,000 credits (5,012,302)SGS LLR Turquoise: Earned 5,000,000 credits (5,000,646)TRP LLR Turquoise: Earned 5,000,000 credits (7,692,745)Woodall LLR Ruby: Earned 2,000,000 credits (2,092,453)Cullen/Woodall Sieve (suspended) Turquoise: Earned 5,000,000 credits (7,892,369)Generalized Cullen/Woodall Sieve Turquoise: Earned 5,000,000 credits (5,460,722)PPS Sieve Double Gold: Earned 500,000,000 credits (745,985,445)TRP Sieve (suspended) Silver: Earned 100,000 credits (121,416)AP 26/27 Jade: Earned 10,000,000 credits (15,343,185)GFN Double Gold: Earned 500,000,000 credits (843,626,870)
Message 120932 - Posted: 5 Oct 2018 | 23:26:33 UTC - in response to Message 120928.
Last modified: 5 Oct 2018 | 23:29:01 UTC

You can find the formula for the expected number of candidates at:
http://www.primegrid.com/forum_thread.php?id=4417&nowrap=true#57237

We have #candidates = e^-gamma * C_n * B_max / log(p_max)
where
C_15 = 5.80266
C_16 = 11.1957
C_17 = 11.0043
C_18 = 13.0078
C_19 = 13.0724
C_20 = 14.5167
C_21 = 16.0846
C_22 = 17.4099


Ooh, nice.

So for C_20, B_max=1E8 and we obtain

#candidates = e^(-0.5772156649) * (14.5167*10^8) / log(p_max)
And in log10:
#candidates = 10^8.5490 /log10(p_max)

For GFN20 50P to 160000P this formula gives a difference of

10^8.5490 /log10(50*10^15)-10^8.5490 /log10(160000*10^15)

= 3677706

It is of course also possible obtain the sieverate from this or vice versa. Nice to see that my shenanigans are working.

PS: it seems my image links from dropbox keep dying...


Nice. Respect. I'll take your word for it. :) :) :)

Edit: just wondering just how many are running that number thru LLR right now!! :D
____________
My lucky number's 1059094^1048576+1 :) and 56414916^16384+1 (GFN-14 Consecutive Prime)

dukebg
Volunteer tester
Avatar
Send message
Joined: 21 Nov 17
Posts: 135
ID: 950482
Credit: 14,676,470
RAC: 97,312
Found 1 prime in the 2018 Tour de Primes321 LLR Gold: Earned 500,000 credits (506,942)Cullen LLR Silver: Earned 100,000 credits (294,623)ESP LLR Gold: Earned 500,000 credits (655,642)Generalized Cullen/Woodall LLR Gold: Earned 500,000 credits (530,908)PPS LLR Gold: Earned 500,000 credits (688,232)PSP LLR Gold: Earned 500,000 credits (561,629)SoB LLR Gold: Earned 500,000 credits (927,999)SR5 LLR Gold: Earned 500,000 credits (505,810)SGS LLR Silver: Earned 100,000 credits (112,037)TRP LLR Gold: Earned 500,000 credits (963,625)Woodall LLR Silver: Earned 100,000 credits (154,039)Generalized Cullen/Woodall Sieve Gold: Earned 500,000 credits (549,916)PPS Sieve Gold: Earned 500,000 credits (701,168)AP 26/27 Silver: Earned 100,000 credits (101,075)GFN Turquoise: Earned 5,000,000 credits (7,417,791)
Message 120936 - Posted: 6 Oct 2018 | 7:41:20 UTC - in response to Message 120928.

PS: it seems my image links from dropbox keep dying...

Yeah, dropbox was never intended for hotlinking like that. You should probably throw the images on imgur. Or, alternatively funkyimg.com also provides image hosting.

Post to thread

Message boards : Sieving : Numerical equation for GFN sieve speed at specific depth

[Return to PrimeGrid main page]
DNS Powered by DNSEXIT.COM
Copyright © 2005 - 2018 Rytis Slatkevičius (contact) and PrimeGrid community. Server load 1.59, 1.24, 1.10
Generated 17 Dec 2018 | 11:53:02 UTC