Author |
Message |
Yves GallotVolunteer developer Project scientist Send message
Joined: 19 Aug 12 Posts: 712 ID: 164101 Credit: 305,166,630 RAC: 0

|
Following Message 130801, I tried to estimate the gap distribution of GF prime numbers.
If the number of GF primes in a range is a Poisson distribution then the gap size is an exponential distribution.
(Because we have the theorem:
If for every t > 0 the number of events in the interval [0, t] follows the Poisson distribution with mean lamba.t, then the sequence of inter-arrivals are independent and identically distributed exponential random variables having mean 1/lamba.)
Let pi be the (expected) number of GF primes in [2; B] and gap_n be the nth gap (sorted in ascending order).
We have: n = pi * (1 - exp(-gap_n/lamba)).
Then gap_n = -lamba * ln(1 - n/pi).
At n = 1, we have gap_min = -lamba * ln(1 - 1/pi) ~ lamba/pi
At n = pi - 1, we have gap_max = lamba * ln(pi).
Let's check the 'theory':
32768:
B_max = 130000000
pi = 1306.67 (real 1357)
lamba = 130000000 / 1306.67 ~ 99500.
gap_min = 99500 / 1306.67 ~ 76 (real 2)
gap_max = 99500 * ln(1306) ~ 714000 (real 678666)
65536:
B_max = 63000000
pi = 637.2 (real 626)
lamba = 63000000 / 637.2 ~ 98900.
gap_min = 98900 / 637.2 ~ 155 (real 126)
gap_max = 98900 * ln(637.2) = 639000 (real 558604)
131072 (low):
B_max = 15000000
pi = 81.52 (real 76)
lamba = 15000000 / 81.52 ~ 184000.
gap_min = 184000 / 81.52 ~ 2257 (real 5068)
gap_max = 184000 * ln(81.52) = 810000 (real 810230)
262144:
B_max = 7700000
pi = 25.86 (real 28)
lamba = 7700000 / 25.86 ~ 298000.
gap_min = 298000 / 25.86 ~ 11500 (real 3558)
gap_max = 298000 * ln(25.86) = 970000 (real 662882 / > 1500000)
That's not bad! Note that the bounds are the most difficult to estimate and that the curves real/estimate gap(n) are very similar.
I will try to improve it: b is even was not taken into account (=> gap_min should be lower) and the distribution isn't a true Poisson distribution because it depends on b. |
|
|
Michael Goetz Volunteer moderator Project administrator
 Send message
Joined: 21 Jan 10 Posts: 13804 ID: 53948 Credit: 345,369,032 RAC: 3,564
                              
|
Following Message 130801, I tried to estimate the gap distribution of GF prime numbers.
If the number of GF primes in a range is a Poisson distribution then the gap size is an exponential distribution.
(Because we have the theorem:
If for every t > 0 the number of events in the interval [0, t] follows the Poisson distribution with mean lamba.t, then the sequence of inter-arrivals are independent and identically distributed exponential random variables having mean 1/lamba.)
Let pi be the (expected) number of GF primes in [2; B] and gap_n be the nth gap (sorted in ascending order).
We have: n = pi * (1 - exp(-gap_n/lamba)).
Then gap_n = -lamba * ln(1 - n/pi).
At n = 1, we have gap_min = -lamba * ln(1 - 1/pi) ~ lamba/pi
At n = pi - 1, we have gap_max = lamba * ln(pi).
Let's check the 'theory':
32768:
B_max = 130000000
pi = 1306.67 (real 1357)
lamba = 130000000 / 1306.67 ~ 99500.
gap_min = 99500 / 1306.67 ~ 76 (real 2)
gap_max = 99500 * ln(1306) ~ 714000 (real 678666)
65536:
B_max = 63000000
pi = 637.2 (real 626)
lamba = 63000000 / 637.2 ~ 98900.
gap_min = 98900 / 637.2 ~ 155 (real 126)
gap_max = 98900 * ln(637.2) = 639000 (real 558604)
131072 (low):
B_max = 15000000
pi = 81.52 (real 76)
lamba = 15000000 / 81.52 ~ 184000.
gap_min = 184000 / 81.52 ~ 2257 (real 5068)
gap_max = 184000 * ln(81.52) = 810000 (real 810230)
262144:
B_max = 7700000
pi = 25.86 (real 28)
lamba = 7700000 / 25.86 ~ 298000.
gap_min = 298000 / 25.86 ~ 11500 (real 3558)
gap_max = 298000 * ln(25.86) = 970000 (real 662882 / > 1500000)
That's not bad! Note that the bounds are the most difficult to estimate and that the curves real/estimate gap(n) are very similar.
I will try to improve it: b is even was not taken into account (=> gap_min should be lower) and the distribution isn't a true Poisson distribution because it depends on b.
Amazingly accurate!
____________
My lucky number is 75898524288+1 |
|
|
Crun-chi Volunteer tester
 Send message
Joined: 25 Nov 09 Posts: 3114 ID: 50683 Credit: 76,797,694 RAC: 5,452
                       
|
Will gap increase as B increase?
____________
92*10^1439761-1 NEAR-REPDIGIT PRIME :) :) :)
4 * 650^498101-1 CRUS PRIME
314187728^131072+1 GENERALIZED FERMAT
Proud member of team Aggie The Pew. Go Aggie! |
|
|
Yves GallotVolunteer developer Project scientist Send message
Joined: 19 Aug 12 Posts: 712 ID: 164101 Credit: 305,166,630 RAC: 0

|
Will gap increase as B increase?
Yes but slowly.
We have pi = C_N / N * Li(B) ~ K_N * B / ln(B)
lambda = B / pi ~ ln(B) / K_N
gap_max ~ ln(B) / K_N * ln(K_N * B / ln(B))
N = 32768, C_32768 = 5.802658835, K_32768 = 0.000177
B = 130000000 => gap_max ~ 750000
B = 400000000 => gap_max ~ 910000
But this is a rough estimate then gap_max is almost the same for B=130M and B=400M. |
|
|
Crun-chi Volunteer tester
 Send message
Joined: 25 Nov 09 Posts: 3114 ID: 50683 Credit: 76,797,694 RAC: 5,452
                       
|
Will gap increase as B increase?
Yes but slowly.
We have pi = C_N / N * Li(B) ~ K_N * B / ln(B)
lambda = B / pi ~ ln(B) / K_N
gap_max ~ ln(B) / K_N * ln(K_N * B / ln(B))
N = 32768, C_32768 = 5.802658835, K_32768 = 0.000177
B = 130000000 => gap_max ~ 750000
B = 400000000 => gap_max ~ 910000
But this is a rough estimate then gap_max is almost the same for B=130M and B=400M.
So only randomness itself can made that gap "looks like" increase"
Thanks Yves, one more good thing to know :)
____________
92*10^1439761-1 NEAR-REPDIGIT PRIME :) :) :)
4 * 650^498101-1 CRUS PRIME
314187728^131072+1 GENERALIZED FERMAT
Proud member of team Aggie The Pew. Go Aggie! |
|
|
Yves GallotVolunteer developer Project scientist Send message
Joined: 19 Aug 12 Posts: 712 ID: 164101 Credit: 305,166,630 RAC: 0

|
I computed the primes b4+1 in [2; 10,000,000]. Because N = 4, the gaps are small and we can 'see' the distribution.
There are 445868 primes in this range and 35321 gap=2, 36565 gap=4, 37619 gap=6, 26814 gap=8, ..., 1 gap=276.
I compared it with the exponential distribution:
D(b) = pi . (exp(2/lambda) - 1) . exp(-b/lambda)
where pi = 445322.4 (the expected number of primes) and lambda = 10000000 / pi ~ 22.45.
In blue the prime gap frequency distribution, in orange the exponential distribution.
|
|
|
|
Yeah, then the gaps look just as if it was a Poisson point process. So this goes against cruncher's logic of the type "a prime in this project is due now" or the opposite. /JeppeSN |
|
|
Crun-chi Volunteer tester
 Send message
Joined: 25 Nov 09 Posts: 3114 ID: 50683 Credit: 76,797,694 RAC: 5,452
                       
|
Yeah, then the gaps look just as if it was a Poisson point process. So this goes against cruncher's logic of the type "a prime in this project is due now" or the opposite. /JeppeSN
If anything is sure about where prime is: I can tell only one word :(true) random (position) :)
____________
92*10^1439761-1 NEAR-REPDIGIT PRIME :) :) :)
4 * 650^498101-1 CRUS PRIME
314187728^131072+1 GENERALIZED FERMAT
Proud member of team Aggie The Pew. Go Aggie! |
|
|
Michael Goetz Volunteer moderator Project administrator
 Send message
Joined: 21 Jan 10 Posts: 13804 ID: 53948 Credit: 345,369,032 RAC: 3,564
                              
|
There's (finally!) another GFN18. Details will likely be released tomorrow.
The gap to this new prime was about 2.2 million.
____________
My lucky number is 75898524288+1 |
|
|