Message boards : Prime Sierpinski Problem : Chance of PSP Prime

 Subscribe SortOldest firstNewest firstHighest rated posts first
Author Message
Roger
Volunteer developer
Volunteer tester

Joined: 27 Nov 11
Posts: 1138
ID: 120786
Credit: 268,638,841
RAC: 1,592

Message 63813 - Posted: 24 Mar 2013 | 5:51:45 UTC

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 100000-110000. 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)

____________

Roger
Volunteer developer
Volunteer tester

Joined: 27 Nov 11
Posts: 1138
ID: 120786
Credit: 268,638,841
RAC: 1,592

Message 64017 - Posted: 1 Apr 2013 | 0:23:37 UTC - in response to Message 63813.

I researched Proth Weight calculation a bit more. There are some enlightening posts on Mersenneforum.org:

"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 n-values of a sieve for this k for n=100001-110000 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."

"The difference between standard Nash weight (w) and modified Nash weight (w') is that the standard Nash weight is computed for n=100001-110000,
while the modified Nash weight is for n=1-10000. 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^n-1.

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

____________

Roger
Volunteer developer
Volunteer tester

Joined: 27 Nov 11
Posts: 1138
ID: 120786
Credit: 268,638,841
RAC: 1,592

Message 64035 - Posted: 2 Apr 2013 | 12:31:07 UTC - in response to Message 64017.

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!
____________

Roger
Volunteer developer
Volunteer tester

Joined: 27 Nov 11
Posts: 1138
ID: 120786
Credit: 268,638,841
RAC: 1,592

Message 73980 - Posted: 3 Mar 2014 | 7:07:58 UTC

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; 14-15M; 15-16M;16-17M; 17-18M;18-19M; 19-20M; 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 Goetz
Volunteer moderator

Joined: 21 Jan 10
Posts: 13835
ID: 53948
Credit: 375,113,310
RAC: 303,929

Message 73984 - Posted: 3 Mar 2014 | 11:58:56 UTC

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 75898524288+1

Roger
Volunteer developer
Volunteer tester

Joined: 27 Nov 11
Posts: 1138
ID: 120786
Credit: 268,638,841
RAC: 1,592

Message 74271 - Posted: 9 Mar 2014 | 3:03:39 UTC

Chance of PSP Prime Table

+---------------+-------+-------+-------+-------+-------+-------+-------+ | k remaining | 14-15M| 15-16M| 16-17M| 17-18M| 18-19M| 19-20M| 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

Joined: 13 Feb 12
Posts: 3122
ID: 130544
Credit: 2,188,715,283
RAC: 191,890

Message 74275 - Posted: 9 Mar 2014 | 13:48:28 UTC

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

Chara34122

Joined: 11 Feb 17
Posts: 95
ID: 490242
Credit: 18,833,291
RAC: 12,817

Message 124013 - Posted: 28 Dec 2018 | 9:52:58 UTC - in response to Message 74271.

Can you write a new table for larger n values?

JeppeSN

Joined: 5 Apr 14
Posts: 1759
ID: 306875
Credit: 47,079,322
RAC: 13,563

Message 124015 - Posted: 28 Dec 2018 | 13:43:31 UTC - in response to Message 74271.

Chance of PSP Prime Table

+---------------+-------+-------+-------+-------+-------+-------+-------+ | k remaining | 14-15M| 15-16M| 16-17M| 17-18M| 18-19M| 19-20M| 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

Roger
Volunteer developer
Volunteer tester

Joined: 27 Nov 11
Posts: 1138
ID: 120786
Credit: 268,638,841
RAC: 1,592

Message 128983 - Posted: 25 Apr 2019 | 2:09:00 UTC

Chance of PSP Prime Table

+---------------+-------+-------+-------+-------+-------+-------+-------+ | k remaining | 20-21M| 21-22M| 22-23M| 23-24M| 24-25M| 25-50M| 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).

Chara34122

Joined: 11 Feb 17
Posts: 95
ID: 490242
Credit: 18,833,291
RAC: 12,817

Message 129619 - Posted: 19 May 2019 | 8:50:33 UTC

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

robish
Volunteer moderator
Volunteer tester

Joined: 7 Jan 12
Posts: 2149
ID: 126266
Credit: 7,067,903,864
RAC: 688,474

Message 129620 - Posted: 19 May 2019 | 9:06:20 UTC - in response to Message 128983.

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 10590941048576+1 and 224584605939537911+81292139*23#*n for n=0..26

Chara34122

Joined: 11 Feb 17
Posts: 95
ID: 490242
Credit: 18,833,291
RAC: 12,817

Message 129636 - Posted: 20 May 2019 | 7:51:56 UTC - in response to Message 129620.

93.36% is chanse of no prime.

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

Roger
Volunteer developer
Volunteer tester

Joined: 27 Nov 11
Posts: 1138
ID: 120786
Credit: 268,638,841
RAC: 1,592

Message 130431 - Posted: 16 Jun 2019 | 8:54:43 UTC - in response to Message 129636.

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 20-21M, 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 1-7 primes. Using the percentages in the last column of the table for the whole range 20-50M 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/no-prime, which gets hard at 3 primes, luckily you can just swap the prime/no-prime 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! / (n-k)!k!
https://betterexplained.com/articles/easy-permutations-and-combinations/
It's useful to calculate the number of combinations, it saved me making a mistake.

Message boards : Prime Sierpinski Problem : Chance of PSP Prime