Join PrimeGrid
Returning Participants
Community
Leader Boards
Results
Other
drummerslowrise

Message boards :
Generalized Fermat Prime Search :
GF prime gap size
Author 
Message 
Yves GallotVolunteer developer Project scientist Send message
Joined: 19 Aug 12 Posts: 553 ID: 164101 Credit: 304,715,793 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 interarrivals 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.  


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 interarrivals 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 75898^{524288}+1
(I am NOT an administrator anymore, so please don't PM me with questions. I can't help.)  

CrunchiVolunteer tester
Send message
Joined: 25 Nov 09 Posts: 2886 ID: 50683 Credit: 55,710,613 RAC: 14,337

Will gap increase as B increase?
____________
314187728^^{131072}+1 GENERALIZED FERMAT :)
93*10^^{1029523}1 REPDIGIT PRIME
31*332^^{367560}+1 CRUS PRIME
Proud member of team Aggie The Pew. Go Aggie!  

Yves GallotVolunteer developer Project scientist Send message
Joined: 19 Aug 12 Posts: 553 ID: 164101 Credit: 304,715,793 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.  

CrunchiVolunteer tester
Send message
Joined: 25 Nov 09 Posts: 2886 ID: 50683 Credit: 55,710,613 RAC: 14,337

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 :)
____________
314187728^^{131072}+1 GENERALIZED FERMAT :)
93*10^^{1029523}1 REPDIGIT PRIME
31*332^^{367560}+1 CRUS PRIME
Proud member of team Aggie The Pew. Go Aggie!  

Yves GallotVolunteer developer Project scientist Send message
Joined: 19 Aug 12 Posts: 553 ID: 164101 Credit: 304,715,793 RAC: 0

I computed the primes b^{4}+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  

CrunchiVolunteer tester
Send message
Joined: 25 Nov 09 Posts: 2886 ID: 50683 Credit: 55,710,613 RAC: 14,337

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) :)
____________
314187728^^{131072}+1 GENERALIZED FERMAT :)
93*10^^{1029523}1 REPDIGIT PRIME
31*332^^{367560}+1 CRUS PRIME
Proud member of team Aggie The Pew. Go Aggie!  


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 75898^{524288}+1
(I am NOT an administrator anymore, so please don't PM me with questions. I can't help.)  

Post to thread
Message boards :
Generalized Fermat Prime Search :
GF prime gap size 