Join PrimeGrid
Returning Participants
Community
Leader Boards
Results
Other
drummerslowrise

Message boards :
Prime Sierpinski Problem :
Chance of PSP Prime
Author 
Message 
RogerVolunteer developer Volunteer tester
Send message
Joined: 27 Nov 11 Posts: 1138 ID: 120786 Credit: 268,621,444 RAC: 0

Lets try and find the chance of finding a PSP Prime.
k remaining ; w = Proth weight
79309 ;; 0.031971828
79817 ;; 0.081642347
152267 ; 0.054237922
156511 ; 0.034826455
168451 ; 0.055950699
222113 ; 0.141018600
225931 ; 0.066798284
237019 ; 0.086780676
The computed weight indicates the asymptotic expected density of primes of the form k*2^n+1. The weight is normalized to the prime number theorem; a coefficient with a weight of 1.00 would have the same density of primes as a randomly chosen set of odd numbers of the same magnitude.
http://www.babybean.com/primes/ProthWeight.html
Note strict definition: Proth weight tells us how many candidates remain after small primes are sieved out of a range where K is given and N is between 100000110000. I am sure our sieves are much deeper than that.
Prime Number Theory say that the chance of a random integer x being prime is about 1/log x
http://primes.utm.edu/howmany.shtml#3
For x = k*2^n+1, chance is about 1/log (k*2^n+1).
That is for random integer, so for remaining PSP k we need to multiply by its Proth weight, so chance is w/log (k*2^n+1) => w/(log k + n * log 2)
____________
 

RogerVolunteer developer Volunteer tester
Send message
Joined: 27 Nov 11 Posts: 1138 ID: 120786 Credit: 268,621,444 RAC: 0

I researched Proth Weight calculation a bit more. There are some enlightening posts on Mersenneforum.org:
http://www.mersenneforum.org/showthread.php?t=11844
"the Nash weight is like an indicator how much prime n's for a special k there could be found.
it's the number of remaining nvalues of a sieve for this k for n=100001110000 and prime factors (sieve depth) up to p=512.
so the higher the Nash weight the more candidates left and the more prime n you could expect."
http://www.mersenneforum.org/showthread.php?t=7213
"The difference between standard Nash weight (w) and modified Nash weight (w') is that the standard Nash weight is computed for n=100001110000,
while the modified Nash weight is for n=110000. The latter is related to the Proth weight: Proth weight = w' / 1751.542"
There are nice some command line tools for calculating Nash and modified Nash weight in that thread as well.
Indeed, I looked at the code in Jack Brennen's Java Applet and found it calculates the modified Nash weight then divides by 1751.542 to come up with the Proth weight.
By modifying the code you can remove the divide by 1751.542 to create a modified Nash weight app, or change the line:
ptab [ n ] = k . shiftLeft ( n ) . add ( BigOne ) ;
to
ptab [ n ] = k . shiftLeft ( n ) . subtract ( BigOne ) ;
to create a Riesel weight Applet. Riesel weight indicates the expected density of primes of the form k*2^n1.
The Proth Weight Applet web page information also says "a coefficient with a weight of 1.00 would have the same density of primes as a randomly chosen set of odd numbers of the same magnitude."
I wondered what would be the average weight of even numbers?
I first tested all odd numbers up to 99,999 and got an average of 0.99978.
Then I tested all even numbers up to 100,000 and got an average of 1.00025.
OK, so any random k (odd or even) will have an average Proth weight of 1.000.
What about Riesel weights?
Testing all odd numbers up to 99,999 gives an average of 0.99983.
Testing all even numbers up to 100,000 gives an average of 1.00049.
So, any random k (odd or even) will also have an average Riesel weight of 1.000.
Are the Proth and Riesel weights for a given k related? Certainly not.
The top Proth weights for all odd k < 100,000 are:
k : 82875, w : 3.431262282
k : 58905, w : 3.3267829147
k : 40755, w : 3.2696903643
k : 54615, w : 3.2542753756
k : 29835, w : 3.1988956017
k : 15345, w : 3.1612145184
k : 5775, w : 3.1600726674
k : 16095, w : 3.1566471144
k : 58305, w : 3.1241043606
k : 68175, w : 3.1212497331
The top Riesel weights for all odd k < 100,000 are:
k : 37785, w : 3.2868181294
k : 58695, w : 3.2439987166
k : 78795, w : 3.234292983
k : 97305, w : 3.1903317191
k : 62985, w : 3.1680656245
k : 53625, w : 3.1332391687
k : 92235, w : 3.1223915841
k : 16995, w : 3.0875651283
k : 2145, w : 3.0544514491
k : 87555, w : 3.0436038645
So going back to my previous post I can now expand the final statement:
The chance of a random integer n for a given Riesel or Proth k being prime is w/(log k + n * log 2), where w is the relevant Riesel or Proth weight.
Notice we ignore the + or  1 because it is insignificant next to the k*2^n for the purposes of calculating probability.
All log's here are log to the base e, i.e. natural logarithm ln(x).
Now usually we are interested in the chance of finding a prime in a given range.
To find the probability for a fixed k over a given range we integrate from n = A to n = B.
Integrating w/(log k + n * log 2) gives w * log(log k + n * log 2)/log 2
So the number of primes, or fraction thereof, expected in a given range n = A to B for a given Riesel or Proth k is:
w * (log(log k + B*log 2)  log(log k + A*log 2))/log 2
____________
 

RogerVolunteer developer Volunteer tester
Send message
Joined: 27 Nov 11 Posts: 1138 ID: 120786 Credit: 268,621,444 RAC: 0

Going back to our PSP k's remaining, the Min in progress is now 14,152,208.
Set A=0, B=14,152,208 and see on average how many primes we should have found by now.
In the last column we set A=0 with 1 prime found and solve for B.
k remaining ; w = Proth weight ; number of primes expected by now ; B = expected first prime
79309 ;; 0.031971828 ; 0.6308016848 ; 42,364,566,600
79817 ;; 0.081642347 ; 1.6107305242 ; 79,225
152267 ; 0.054237922 ; 1.0657115500 ; 6,111,008
156511 ; 0.034826455 ; 0.6841833789 ; 7,597,207,653
168451 ; 0.055950699 ; 1.0986852383 ; 4,167,441
222113 ; 0.141018600 ; 2.7645131309 ; 2,404
225931 ; 0.066798284 ; 1.3093728933 ; 570,960
237019 ; 0.086780676 ; 1.7005800087 ; 52,537
Remember these are the only k's remaining after all others have had a prime found, so there is a really strong selection bias working against them.
Finally we can see what the chance of finding a prime is for the coming ranges for each k:
k remaining ; 14.0M  15.0M ; 15.0M  16.0M ; 16.0M  17.0M ; 17.0M  18.0M ; 18.0M  19.0M ; 19.0M  20.0M
79309 ;; 0.0031823339 ; 0.0029768747 ; 0.0027963442 ; 0.0026364635 ; 0.0024938807 ; 0.0023659319
79817 ;; 0.0081263169 ; 0.0076016623 ; 0.0071406646 ; 0.0067323980 ; 0.0063683025 ; 0.0060415761
152267 ; 0.0053986017 ; 0.0050500550 ; 0.0047437978 ; 0.0044725718 ; 0.0042306902 ; 0.0040136342
156511 ; 0.0034664705 ; 0.0032426669 ; 0.0030460175 ; 0.0028718619 ; 0.0027165484 ; 0.0025771756
168451 ; 0.0055690838 ; 0.0052095304 ; 0.0048936020 ; 0.0046138109 ; 0.0043642910 ; 0.0041403806
222113 ; 0.0140363641 ; 0.0131301428 ; 0.0123338741 ; 0.0116286866 ; 0.0109997945 ; 0.0104354489
225931 ; 0.0066488040 ; 0.0062195413 ; 0.0058423614 ; 0.0055083252 ; 0.0052104289 ; 0.0049431073
237019 ; 0.0086377624 ; 0.0080800877 ; 0.0075900763 ; 0.0071561147 ; 0.0067691042 ; 0.0064218146
Total chance ; 5.50% ; 5.15% ; 4.83% ; 4.56% ; 4.31% ; 4.09%
Happy crunching!
____________
 

RogerVolunteer developer Volunteer tester
Send message
Joined: 27 Nov 11 Posts: 1138 ID: 120786 Credit: 268,621,444 RAC: 0

I calculated the chances of PSP prime being found using my new formula for weight, i.e.
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" The new weight formula should better reflect density of primes for a randomly chosen set of odd numbers of the same magnitude as our sieving test range (n=100001 to 110000).
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
Min in progress now 14,900,220.
k remaining ; P1e6 ; w = weight ; number of primes expected by now ; n = expected first prime
79309 ;; 28 ; 0.0659 ; 1.6 ; 36,950
79817 ;; 74 ; 0.1742 ; 4.2 ; 54
152267 ; 41 ; 0.0992 ; 2.4 ; 1,085
156511 ; 24 ; 0.0581 ; 1.4 ; 151,000
168451 ; 42 ; 0.1020 ; 2.4 ; 893
222113 ;113; 0.2776 ; 6.6 ; 13
225931 ; 54 ; 0.1328 ; 3.2 ; 186
237019 ; 66 ; 0.1626 ; 3.9 ; 72
Chances with new weight formula look about double that of previous, so good news.
k remaining ;
n=10e6; 1415M; 1516M;1617M; 1718M;1819M; 1920M; Total
79309 ;; 0.66% ; 0.61% ; 0.58% ; 0.54% ; 0.51% ; 0.49% ; 3.39%
79817 ;; 1.73% ; 1.62% ; 1.52% ; 1.44% ; 1.36% ; 1.29% ; 8.97%
152267 ; 0.99% ; 0.92% ; 0.87% ; 0.82% ; 0.77% ; 0.73% ; 5.10%
156511 ; 0.58% ; 0.54% ; 0.51% ; 0.48% ; 0.45% ; 0.43% ; 2.99%
168451 ; 1.02% ; 0.95% ; 0.89% ; 0.84% ; 0.80% ; 0.75% ; 5.25%
222113 ; 2.76% ; 2.58% ; 2.43% ; 2.29% ; 2.17% ; 2.05% ; 14.29%
225931 ; 1.32% ; 1.24% ; 1.16% ; 1.09% ; 1.04% ; 0.98% ; 6.83%
237019 ; 1.62% ; 1.51% ; 1.42% ; 1.34% ; 1.27% ; 1.20% ; 8.43%
Total ;;; 10.67% ; 9.99% ; 9.38% ; 8.84% ; 8.37% ; 7.94% ; 55.18%
Best of luck!  

Michael GoetzVolunteer moderator Project administrator
Send message
Joined: 21 Jan 10 Posts: 13807 ID: 53948 Credit: 346,792,940 RAC: 91,262

Hint: If you want to do tables, you can use the [ pre ] tags. That produces a fixed pitch font which makes it much easier. You can also use tabs to align the columns rather than getting all the spaces exactly right.
____________
My lucky number is 75898^{524288}+1  

RogerVolunteer developer Volunteer tester
Send message
Joined: 27 Nov 11 Posts: 1138 ID: 120786 Credit: 268,621,444 RAC: 0

Chance of PSP Prime Table
+++++++++
 k remaining  1415M 1516M 1617M 1718M 1819M 1920M Total 
+++++++++
 79309  0.66%  0.61%  0.58%  0.54%  0.51%  0.49%  3.39% 
 79817  1.73%  1.62%  1.52%  1.44%  1.36%  1.29%  8.97% 
 152267  0.99%  0.92%  0.87%  0.82%  0.77%  0.73%  5.10% 
 156511  0.58%  0.54%  0.51%  0.48%  0.45%  0.43%  2.99% 
 168451  1.02%  0.95%  0.89%  0.84%  0.80%  0.75%  5.25% 
 222113  2.76%  2.58%  2.43%  2.29%  2.17%  2.05%  14.29%
 225931  1.32%  1.24%  1.16%  1.09%  1.04%  0.98%  6.83% 
 237019  1.62%  1.51%  1.42%  1.34%  1.27%  1.20%  8.43% 
+++++++++
 Total  10.67% 9.99%  9.38%  8.84%  8.37%  7.94%  55.18%
+++++++++  

Dave Send message
Joined: 13 Feb 12 Posts: 3075 ID: 130544 Credit: 2,175,498,306 RAC: 1,535,244

Shouldn't the "total" be an "average"?  


Can you write a new table for larger n values?  


Chance of PSP Prime Table
+++++++++
 k remaining  1415M 1516M 1617M 1718M 1819M 1920M Total 
+++++++++
 79309  0.66%  0.61%  0.58%  0.54%  0.51%  0.49%  3.39% 
 79817  1.73%  1.62%  1.52%  1.44%  1.36%  1.29%  8.97% 
 152267  0.99%  0.92%  0.87%  0.82%  0.77%  0.73%  5.10% 
 156511  0.58%  0.54%  0.51%  0.48%  0.45%  0.43%  2.99% 
 168451  1.02%  0.95%  0.89%  0.84%  0.80%  0.75%  5.25% 
 222113  2.76%  2.58%  2.43%  2.29%  2.17%  2.05%  14.29%
 225931  1.32%  1.24%  1.16%  1.09%  1.04%  0.98%  6.83% 
 237019  1.62%  1.51%  1.42%  1.34%  1.27%  1.20%  8.43% 
+++++++++
 Total  10.67% 9.99%  9.38%  8.84%  8.37%  7.94%  55.18%
+++++++++
I do not know if the Total cells are the most meaningful way to calculate it. But it is interesting to notice that out of those eight multipliers shown here, it turned out that one had a prime with n < 20M. See green row in the table at /stats_psp_llr.php. /JeppeSN  

RogerVolunteer developer Volunteer tester
Send message
Joined: 27 Nov 11 Posts: 1138 ID: 120786 Credit: 268,621,444 RAC: 0

Chance of PSP Prime Table
+++++++++
 k remaining  2021M 2122M 2223M 2324M 2425M 2550M Total 
+++++++++
 79309  0.46%  0.44%  0.42%  0.40%  0.39%  6.59%  8.71% 
 79817  1.23%  1.17%  1.12%  1.07%  1.03%  17.42% 23.03%
 152267  0.70%  0.67%  0.64%  0.61%  0.58%  9.92%  13.11%
 156511  0.41%  0.39%  0.37%  0.36%  0.34%  5.81%  7.68% 
 222113  1.95%  1.86%  1.78%  1.70%  1.63%  27.76% 36.70%
 225931  0.93%  0.89%  0.85%  0.82%  0.78%  13.28% 17.56%
 237019  1.14%  1.09%  1.04%  1.00%  0.96%  16.26% 21.49%
+++++++++
 Any Prime  6.64%  6.34%  6.07%  5.81%  5.58%  65.67% 76.91%
+++++++++
Updated table for new range and removal of k=168451.
Total row at the bottom is calculated as 1(chance of no prime).  


And is it hard to calculate the possibility of at least 2 primes before 50M?  

robishVolunteer moderator Volunteer tester
Send message
Joined: 7 Jan 12 Posts: 2144 ID: 126266 Credit: 6,918,527,813 RAC: 3,673,868

Total row at the bottom is calculated as 1(chance of no prime).
Hi Roger
I find that confusing. Does that mean on the 1st column theres a 93.36% chance of finding one in that range?
____________
My lucky numbers 1059094^{1048576}+1 and 224584605939537911+81292139*23#*n for n=0..26  


93.36% is chanse of no prime.
If I did not make any mistake the chanse of 2 or more primes is 37.53%  

RogerVolunteer developer Volunteer tester
Send message
Joined: 27 Nov 11 Posts: 1138 ID: 120786 Credit: 268,621,444 RAC: 0

93.36% is chanse of no prime.
If I did not make any mistake the chanse of 2 or more primes is 37.53%
First part is correct.
1  0.0664 = 0.9336 which is the chance no prime is found 2021M, i.e. 93.36%.
There is a chance of 0,1,2,3,4,5,6 or 7 primes. Mostly we are interested in the chance of finding a prime, as opposed to no prime, which includes finding 17 primes. Using the percentages in the last column of the table for the whole range 2050M I calculated:
Chance of no prime: 23.09%
Chance of 1 prime: 39.14%
Chance of 2 primes: 26.43%
Chance of 3 primes: 9.280%
Chance of 4 primes: 1.835%
Chance of 5 primes: 0.2045%
Chance of 6 primes: 0.01190%
Chance of 7 primes: 0.000280%
To calculate the chances you have to go through all the combinations of prime/noprime, which gets hard at 3 primes, luckily you can just swap the prime/noprime percentages to calculate for 4 primes. The number of combination formula, or the number of ways to combine k items from a set of n is n! / (nk)!k!
https://betterexplained.com/articles/easypermutationsandcombinations/
It's useful to calculate the number of combinations, it saved me making a mistake.  

Message boards :
Prime Sierpinski Problem :
Chance of PSP Prime 