Join PrimeGrid
Returning Participants
Community
Leader Boards
Results
Other
drummers-lowrise
|
Message boards :
Sierpinski/Riesel Base 5 Problem :
Chance of SR5 Prime
| Author |
Message |
|---|
 RogerVolunteer developer
Volunteer tester
Send message
Joined: 27 Nov 11
Posts: 1138
ID: 120786
Credit: 268,668,824
RAC: 0
                    
|
|
For all the SR5 k's I calculated their Nash weight and the probability of there being a prime from the PRPNet leading edge 938,000 to 1M and for BOINC from 1M to 2M.
form ; Nash ; w ; Chance to 1M ; Chance to 2M
100186*5^n-1 ; 430 ; 0.2454979669 ; 0.96% ; 10.57%
102818*5^n-1 ; 396 ; 0.2260864998 ; 0.89% ; 9.74%
102952*5^n-1 ; 244 ; 0.1393058231 ; 0.54% ; 6.00%
102976*5^n-1 ; 421 ; 0.2403596374
104944*5^n-1 ; 679 ; 0.3876584176 ; 1.52% ; 16.70%
105464*5^n+1 ; 566 ; 0.3231438355 ; 1.27% ; 13.92%
10918*5^n+1 ; 305 ; 0.1741322789 ; 0.68% ; 7.50%
109208*5^n+1 ; 225 ; 0.1284582385 ; 0.51% ; 5.53%
109238*5^n-1 ; 202 ; 0.1153269519 ; 0.45% ; 4.97%
109838*5^n-1 ; 155 ; 0.0884934532 ; 0.34% ; 3.81%
109862*5^n-1 ; 261 ; 0.1490115567 ; 0.58% ; 6.42%
110488*5^n+1 ; 565 ; 0.32257291
114986*5^n-1 ; 259 ; 0.1478697057 ; 0.58% ; 0.47% chance to 1,052,966
11812*5^n-1 ; 198 ; 0.1130432499
118568*5^n+1 ; 382 ; 0.2180935427 ; 0.86% ; 9.39%
119878*5^n-1 ; 291 ; 0.1661393218 ; 0.65% ; 0.20% chance to 1,019,645
126134*5^n+1 ; 175 ; 0.0999119633 ; 0.39% ; 4.30%
127174*5^n-1 ; 413 ; 0.2357922334 ; 0.92% ; 10.15%
130484*5^n-1 ; 464 ; 0.2649094341 ; 1.03% ; 11.41%
131848*5^n-1 ; 413 ; 0.2357922334 ; 0.92% ; 10.15%
133778*5^n+1 ; 477 ; 0.2723314656 ; 1.07% ; 11.73%
134266*5^n-1 ; 393 ; 0.2243737233 ; 0.88% ; 9.66%
136804*5^n-1 ; 663 ; 0.3785236095 ; 1.48% ; 16.30%
138172*5^n-1 ; 302 ; 0.1724195024 ; 0.68% ; 7.43%
138514*5^n+1 ; 250 ; 0.1427313761 ; 0.56% ; 6.15%
139196*5^n+1 ; 274 ; 0.1564335882 ; 0.61% ; 6.74%
1396*5^n-1 ; 320 ; 0.1826961614 ; 0.72% ; 7.87%
143632*5^n-1 ; 503 ; 0.2871755288 ; 1.12% ; 12.37%
144052*5^n+1 ; 253 ; 0.1444441526 ; 0.57% ; 6.22%
145462*5^n-1 ; 428 ; 0.2443561159 ; 0.96% ; 10.52%
145484*5^n-1 ; 366 ; 0.2089587346 ; 0.82% ; 9.00%
146264*5^n-1 ; 1118 ; 0.638294714 ; 2.51% ; 27.49%
146756*5^n-1 ; 722 ; 0.4122082142 ; 1.62% ; 17.75%
147844*5^n-1 ; 436 ; 0.2489235200 ; 0.98% ; 10.72%
150344*5^n-1 ; 420 ; 0.2397887119 ; 0.94% ; 10.33%
151042*5^n-1 ; 191 ; 0.1090467714 ; 0.43% ; 4.70%
152428*5^n-1 ; 462 ; 0.2637675831 ; 1.03% ; 11.36%
152588*5^n+1 ; 537 ; 0.3065869959 ; 1.20% ; 13.20%
154222*5^n+1 ; 956 ; 0.5458047823 ; 2.14% ; 23.51%
154844*5^n-1 ; 576 ; 0.3288530906 ; 1.29% ; 14.16%
159388*5^n-1 ; 478 ; 0.2729023912 ; 1.07% ; 11.75%
162434*5^n-1 ; 454 ; 0.259200179
162668*5^n-1 ; 494 ; 0.2820371992
164852*5^n-1 ; 593 ; 0.3385588242 ; 1.33% ; 14.58%
170386*5^n-1 ; 585 ; 0.3339914201 ; 1.31% ; 14.38%
170908*5^n-1 ; 435 ; 0.2483525945 ; 0.98% ; 10.70%
171362*5^n-1 ; 447 ; 0.2552037005 ; 1.00% ; 10.99%
17152*5^n-1 ; 756 ; 0.4316196814 ; 1.69% ; 18.59%
173198*5^n-1 ; 394 ; 0.2249446488 ; 0.88% ; 9.69%
174344*5^n-1 ; 494 ; 0.2820371992
175124*5^n-1 ; 661 ; 0.3773817585 ; 1.48% ; 16.25%
177742*5^n-1 ; 1027 ; 0.586340493 ; 2.30% ; 25.25%
178658*5^n-1 ; 496 ; 0.2831790502 ; 1.11% ; 12.20%
180062*5^n-1 ; 718 ; 0.4099245122 ; 1.61% ; 17.65%
182398*5^n-1 ; 289 ; 0.1649974708 ; 0.65% ; 7.11%
18656*5^n-1 ; 279 ; 0.1592882158
187916*5^n-1 ; 126 ; 0.0719366136 ; 0.28% ; 3.10%
189766*5^n-1 ; 507 ; 0.2894592308 ; 1.14% ; 12.47%
190334*5^n-1 ; 281 ; 0.1604300668 ; 0.63% ; 6.91%
194368*5^n-1 ; 488 ; 0.2786116462 ; 1.09% ; 12.00%
195872*5^n-1 ; 753 ; 0.4299069049 ; 1.69% ; 18.51%
201778*5^n-1 ; 657 ; 0.3750980565 ; 1.47% ; 16.15%
204394*5^n-1 ; 182 ; 0.1039084418 ; 0.41% ; 4.48%
206894*5^n-1 ; 291 ; 0.1661393218 ; 0.65% ; 7.16%
207394*5^n-1 ; 266 ; 0.1518661842 ; 0.60% ; 6.54%
207494*5^n-1 ; 296 ; 0.1689939493 ; 0.66% ; 7.28%
213988*5^n-1 ; 393 ; 0.2243737233 ; 0.88% ; 9.66%
22478*5^n-1 ; 717 ; 0.4093535867 ; 1.61% ; 17.63%
22934*5^n-1 ; 420 ; 0.2397887119 ; 0.94% ; 10.33%
231674*5^n-1 ; 255 ; 0.1455860036 ; 0.57% ; 6.27%
238694*5^n-1 ; 194 ; 0.1107595479 ; 0.43% ; 4.77%
23906*5^n-1 ; 218 ; 0.1244617600 ; 0.49% ; 5.36%
239062*5^n-1 ; 294 ; 0.1678520983 ; 0.66% ; 7.23%
239342*5^n-1 ; 399 ; 0.2277992763 ; 0.89% ; 9.81%
24032*5^n+1 ; 526 ; 0.3003068154 ; 1.18% ; 12.93%
243686*5^n-1 ; 368 ; 0.2101005857 ; 0.82% ; 9.05%
243944*5^n-1 ; 496 ; 0.2831790502 ; 1.11% ; 12.20%
245114*5^n-1 ; 349 ; 0.1992530011 ; 0.78% ; 8.58%
246238*5^n-1 ; 251 ; 0.1433023016 ; 0.56% ; 6.17%
248546*5^n-1 ; 571 ; 0.3259984631 ; 1.28% ; 14.04%
2488*5^n-1 ; 563 ; 0.321431059
256612*5^n-1 ; 234 ; 0.1335965681 ; 0.52% ; 5.75%
259072*5^n-1 ; 586 ; 0.3345623456 ; 1.31% ; 14.41%
262172*5^n-1 ; 272 ; 0.1552917372
26222*5^n-1 ; 589 ; 0.3362751221 ; 1.32% ; 14.48%
265702*5^n-1 ; 228 ; 0.1301710150 ; 0.51% ; 5.61%
267298*5^n-1 ; 333 ; 0.1901181930 ; 0.74% ; 8.19%
26798*5^n+1 ; 413 ; 0.2357922334 ; 0.93% ; 10.15%
268514*5^n-1 ; 425 ; 0.2426433394 ; 0.95% ; 10.45%
271162*5^n-1 ; 236 ; 0.1347384191 ; 0.52% ; 5.80%
273662*5^n-1 ; 331 ; 0.1889763420 ; 0.74% ; 8.14%
27994*5^n-1 ; 635 ; 0.3625376954
285598*5^n-1 ; 840 ; 0.4795774238 ; 1.88% ; 20.65%
285728*5^n-1 ; 81 ;: 0.0462449659 ; 0.18% ; 1.99%
289184*5^n-1 ; 582 ; 0.3322786436
296024*5^n-1 ; 210 ; 0.1198943559 ; 0.47% ; 5.16%
298442*5^n-1 ; 310 ; 0.1769869064 ; 0.69% ; 7.62%
29914*5^n+1 ; 353 ; 0.2015367031 ; 0.79% ; 8.68%
301562*5^n-1 ; 272 ; 0.1552917372 ; 0.61% ; 6.69%
304004*5^n-1 ; 509 ; 0.2906010818 ; 1.14% ; 12.52%
305716*5^n-1 ; 291 ; 0.1661393218 ; 0.65% ; 7.16%
306398*5^n-1 ; 323 ; 0.1844089380 ; 0.72% ; 7.94%
313126*5^n-1 ; 895 ; 0.5109783265 ; 2.01% ; 22.01%
316594*5^n-1 ; 353 ; 0.2015367031
31712*5^n+1 ; 374 ; 0.2135261387 ; 0.84% ; 9.20%
318278*5^n-1 ; 193 ; 0.1101886224 ; 0.43% ; 4.75%
322498*5^n-1 ; 1150 ; 0.656564330 ; 2.58% ; 28.28%
325918*5^n-1 ; 577 ; 0.3294240161 ; 1.29% ; 14.19%
325922*5^n-1 ; 493 ; 0.2814662737 ; 1.10% ; 12.12%
326834*5^n-1 ; 305 ; 0.1741322789 ; 0.68% ; 7.50%
327926*5^n-1 ; 409 ; 0.2335085313 ; 0.92% ; 10.06%
329584*5^n-1 ; 148 ; 0.0844969747 ; 0.33% ; 3.64%
330286*5^n-1 ; 608 ; 0.3471227067 ; 1.36% ; 14.95%
331882*5^n-1 ; 434 ; 0.247781669
335414*5^n-1 ; 377 ; 0.2152389152 ; 0.84% ; 9.27%
338866*5^n-1 ; 191 ; 0.1090467714 ; 0.43% ; 4.70%
338948*5^n-1 ; 276 ; 0.1575754392
340168*5^n-1 ; 435 ; 0.2483525945
35248*5^n-1 ; 113 ; 0.0645145820 ; 0.25% ; 2.78%
35816*5^n-1 ; 559 ; 0.3191473570 ; 1.25% ; 13.74%
3622*5^n-1 ; 526 ; 0.3003068154 ; 1.17% ; 12.93%
36412*5^n+1 ; 514 ; 0.2934557093 ; 1.15% ; 12.64%
37292*5^n+1 ; 291 ; 0.1661393218 ; 0.65% ; 7.16%
41738*5^n+1 ; 652 ; 0.3722434289 ; 1.46% ; 16.03%
44348*5^n+1 ; 556 ; 0.3174345805 ; 1.24% ; 13.67%
44738*5^n+1 ; 751 ; 0.4287650539 ; 1.68% ; 18.47%
45748*5^n+1 ; 557 ; 0.3180055060 ; 1.25% ; 13.70%
48764*5^n-1 ; 212 ; 0.121036207
4906*5^n-1 ; 478 ; 0.2729023912 ; 1.07% ; 11.75%
49568*5^n-1 ; 503 ; 0.2871755288
51208*5^n+1 ; 490 ; 0.2797534972 ; 1.10% ; 12.05%
52922*5^n-1 ; 352 ; 0.2009657776 ; 0.79% ; 8.66%
53546*5^n-1 ; 650 ; 0.3711015779 ; 1.46% ; 15.98%
5374*5^n-1 ; 673 ; 0.3842328645
55154*5^n+1 ; 518 ; 0.2957394113 ; 1.16% ; 12.74%
57406*5^n-1 ; 411 ; 0.2346503823
58642*5^n+1 ; 333 ; 0.1901181930 ; 0.75% ; 8.19%
59912*5^n+1 ; 1065 ; 0.608035662 ; 2.38% ; 26.19%
60394*5^n+1 ; 402 ; 0.2295120528 ; 0.90% ; 9.88%
62698*5^n+1 ; 753 ; 0.4299069049 ; 1.69% ; 18.51%
63838*5^n-1 ; 505 ; 0.2883173798 ; 1.13% ; 12.42%
64258*5^n+1 ; 435 ; 0.2483525945 ; 0.97% ; 10.70%
6436*5^n+1 ; 571 ; 0.3259984631 ; 1.28% ; 14.04%
64598*5^n-1 ; 384 ; 0.2192353937 ; 0.86% ; 9.44%
66916*5^n-1 ; 515 ; 0.2940266348 ; 1.15% ; 12.66%
67612*5^n+1 ; 464 ; 0.2649094341 ; 1.04% ; 11.41%
67748*5^n+1 ; 331 ; 0.1889763420 ; 0.74% ; 8.14%
68132*5^n-1 ; 143 ; 0.0816423471 ; 0.32% ; 3.52%
70082*5^n-1 ; 752 ; 0.4293359794
71146*5^n-1 ; 397 ; 0.2266574253 ; 0.89% ; 9.76%
71492*5^n+1 ; 221 ; 0.1261745365 ; 0.50% ; 5.43%
72532*5^n-1 ; 383 ; 0.2186644682
74632*5^n+1 ; 565 ; 0.3225729100 ; 1.27% ; 13.89%
7528*5^n+1 ; 313 ; 0.1786996829 ; 0.70% ; 7.70%
76354*5^n-1 ; 168 ; 0.0959154848 ; 0.37% ; 4.13%
76724*5^n+1 ; 438 ; 0.2500653710 ; 0.98% ; 10.77%
77072*5^n+1 ; 159 ; 0.0907771552 ; 0.36% ; 3.91%
81134*5^n-1 ; 552 ; 0.3151508785 ; 1.23% ; 13.57%
81556*5^n+1 ; 527 ; 0.3008777409 ; 1.18% ; 12.96%
83936*5^n+1 ; 428 ; 0.2443561159 ; 0.96% ; 10.52%
84284*5^n+1 ; 359 ; 0.2049622561 ; 0.80% ; 8.83%
84466*5^n-1 ; 924 ; 0.5275351662 ; 2.07% ; 22.72%
88444*5^n-1 ; 704 ; 0.4019315552 ; 1.58% ; 17.31%
90056*5^n+1 ; 398 ; 0.2272283508 ; 0.89% ; 9.79%
92158*5^n+1 ; 203 ; 0.1158978774 ; 0.45% ; 4.99%
92182*5^n+1 ; 354 ; 0.2021076286 ; 0.80% ; 8.70%
92906*5^n+1 ; 347 ; 0.1981111501 ; 0.77% ; 8.53%
92936*5^n-1 ; 740 ; 0.4224848733 ; 1.66% ; 18.20%
93484*5^n+1 ; 655 ; 0.3739562054 ; 1.47% ; 16.11%
97366*5^n-1 ; 676 ; 0.3859456410 ; 1.52% ; 16.62%
97768*5^n-1 ; 320 ; 0.1826961614 ; 0.72% ; 7.87%
According to this we will, on average, find primes for 1.5 k's in PRPNet to 1M and 16.3 k's in BOINC to 2M.
Those k's with no % chance are ones where primes have already been found in PRPNet.
The tools I used previously only covers base 2. You can use srsieve to find weights for any base, for example:
srsieve -n 100001 -N 110000 -P 511 "97768*5^n-1"
Reference: http://www.mersenneforum.org/showthread.php?t=14303
Software: http://www.mersenneforum.org/showthread.php?t=9742
The number of primes, or fraction thereof, expected in a given range n = A to B for a given k, k*b^n+/-1 is:
w * (log(log k + B*log b) - log(log k + A*log b))/log b
Note that odd k's have all terms divisible by 2, that's why we only have even k's in SR5.
I also created a batch file that can calulate weights for k's over a range:
set /a num=1
del output.txt
:next
set /a kvalue=%num%+%num%
REM echo Finding Nash weight for %kvalue%*5^n-1:
srsieve-x86_64-windows.exe -q -n 100001 -N 110000 -P 511 "%kvalue%*5^n-1" >> output.txt
findstr /R /N "^" srsieve.out | find /C ":" > tmpfile.txt
set /p weight= < tmpfile.txt
del tmpfile.txt
set /a weight=%weight%-2
echo Nash weight for %kvalue%*5^^n-1: %weight% >> output.txt
set /a num=%num%+1
if %num% LEQ %1 goto next
First 500 k*5^n-1 weights average: 2204
First 500 k*5^n+1 weights average: 2235
Base 2 weights average: 1751, so base 5 should be easier overall
____________
 | |
|
RogerVolunteer developer
Volunteer tester
Send message
Joined: 27 Nov 11
Posts: 1138
ID: 120786
Credit: 268,668,824
RAC: 0
|
|
My old chance of prime equation used weight w as the Nash weight divided by 1751.542 giving a coefficient of 1.00 for the average k of base 2.
The trouble was it assumed base 2 had the same density of primes as a randomly chosen set of odd numbers of the same magnitude.
I started from the basics. To find the weight of the term b*k*n-1 I used Prime Number Theory which says that the chance of a random integer x being prime is about 1/log x
For x = b*k*n-1, chance is about 1/log (b*k*n-1)
To find the probability for a fixed k over a given range we integrate from n = A to n = B.
Integrating 1/log (b*k*n-1) gives li(b*k*n-1)/(k*b), where li() is the logarithmic integral.
So the number of primes, or fraction thereof, expected in a given range n = A to B for b*k*n-1 is:
(li(b*k*B-1)-li(b*k*A-1))/(k*b)
To calculate our weight we're going to sieve test A=100001 and B=110000:
w = k*b*P1e6 / (li(110,000*k*b)-li(100,001*k*b))
Where P1e6 is the number of candidates remaining after testing the range n=100001 to 110000 for factors up to 1 million.
> srsieve -n 100001 -N 110000 -P 1e6 "k*b^n+/-1"
It is similar to the Nash weight but sieved to a deeper depth to be more accurate and not skewed toward small factors.
li(X) is the logarithmic integral.
li(x) ∼ x/ln(x) + x/ln(x)² + 2x/ln(x)³ + 6x/ln(x)⁴ + 24x/ln(x)⁵ + ...
The weight is fixed for a fixed k. To use it we plug it into the same formula:
#Primes = w * (ln(ln k + B*ln b) - ln(ln k + A*ln b))/ln b
I've used this improved weight to calculate the chance of primes for the SR5 project from n=1M to 2M: http://rogerkarpin.wix.com/thecount123ks#!sr5/cy5b
Chances are improved compared to the old weight formula. If we sum the chances we're now expecting 31 primes in the n=1M to 2M range.
I checked the values coming out of my formula for a number of bases and their about 98% correlated with the method they use on CRUS.
Advantage of my method is you don't need the sieve results to calculate the chance of primes.
Want to know more? Yves Gallot did a paper on the subject: http://yves.gallot.pagesperso-orange.fr/papers/weight.pdf | |
|
Michael Goetz Volunteer moderator
Project administrator
Send message
Joined: 21 Jan 10
Posts: 13952
ID: 53948
Credit: 391,849,676
RAC: 147,542
                            
|
If we sum the chances we're now expecting 31 primes in the n=1M to 2M range.
We found 17 primes between n=1M and n=1.5M, which correlates very closely with your result.
One thing I think you left out of your calculations, however, is that unlike, say, the PPS Proth search, every time we find a prime we stop searching that k. Therefore, as primes are found, the odds of finding more primes within a specific n range will drop because we're searching fewer numbers in that range. There are likely primes we're "missing" (because we're not interested in finding them) at higher n's for k's we've already eliminated.
As more and more k's are eliminated this will become a larger factor. With one k out of 100 k's eliminated, the number of tests drops by ~1%. When the next to last k is eliminated, the number of tests drops by ~50%.
____________
My lucky number is 75898524288+1 | |
|
RogerVolunteer developer
Volunteer tester
Send message
Joined: 27 Nov 11
Posts: 1138
ID: 120786
Credit: 268,668,824
RAC: 0
|
|
31.2 is the average amount that will be found. We could find more, we could find less.
Agreed that we could find more than 1 prime for a k if we tested all 1-2M regardless of prime being found. 31.2 is based on continued testing.
Realise that we will find more in the 1-1.5 range than 1.5-2M.
Plugging the numbers in and assuming and we keep testing all the 150 k's regardless of prime find we should expect:
18.2 primes in the range 1-1.5M on average;
12.9 in the 1.5-2M range;
18.2 in the 2-3M range;
12.9 in the 3-4M range;
...
Now if you reduce the fraction of the k's by stopping testing we should expect:
18.2 primes in the range 1-1.5M on average; 131.8 k's left
12.9*131.8/150 = 11.3 in the 1.5-2M range; 120.5k's left
18.2*120.5/150 = 14.6 in the 2-3M range; 105.9k's left
12.9*105.9/150 = 9.1 in the 3-4M range; 96.8k's left
...
Simplistic but you get the idea. | |
|
RogerVolunteer developer
Volunteer tester
Send message
Joined: 27 Nov 11
Posts: 1138
ID: 120786
Credit: 268,668,824
RAC: 0
|
|
Removing k's at 0.5M/1M boundary is arbitrary. In reality a k is removed once a prime is found.
So I tested a range size until average chance of prime = 1.00, then removed a k and repeated.
I removed k's starting from the top of the list because I want a method that assumes no prior knowledge of the results.
Using this I found:
17 primes in the 1-1.5M range;
11 in the 1.5-2M range;
14 in the 2-3M range; and
9 in the 3-4M range.
Happy Crunching! | |
|
|
|
Removing k's at 0.5M/1M boundary is arbitrary. In reality a k is removed once a prime is found.
So I tested a range size until average chance of prime = 1.00, then removed a k and repeated.
I removed k's starting from the top of the list because I want a method that assumes no prior knowledge of the results.
Using this I found:
17 primes in the 1-1.5M range;
11 in the 1.5-2M range;
14 in the 2-3M range; and
9 in the 3-4M range.
Happy Crunching!
I can tell you, that using the percent of k's removed on both Sierpinski aswell as the Riesel side (in the n=750K to n=1.5M range), I came out with a total removal of ~26.x primed k's in the range from n=1.5M to n=3.0M and I can see that you have an expectancy of 25, so despite doing this independent of one another, we came back with very similar results :)
Take care
Kenneth | |
|
Message boards :
Sierpinski/Riesel Base 5 Problem :
Chance of SR5 Prime |
