Other

drummers-lowrise

Message boards : Generalized Fermat Prime Search : GF prime gap size

 Subscribe SortOldest firstNewest firstHighest rated posts first
Author Message
Yves Gallot
Volunteer developer
Project scientist

Joined: 19 Aug 12
Posts: 644
ID: 164101
Credit: 305,010,093
RAC: 78 Message 130897 - Posted: 6 Jul 2019 | 11:34:16 UTC

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.

Message 130903 - Posted: 6 Jul 2019 | 15:01:28 UTC - in response to Message 130897.

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

Message 130904 - Posted: 6 Jul 2019 | 15:25:50 UTC - in response to Message 130903.

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

Yves Gallot
Volunteer developer
Project scientist

Joined: 19 Aug 12
Posts: 644
ID: 164101
Credit: 305,010,093
RAC: 78 Message 130906 - Posted: 6 Jul 2019 | 16:36:15 UTC - in response to Message 130904.

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.

Message 130907 - Posted: 6 Jul 2019 | 16:54:43 UTC - in response to Message 130906.

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

Yves Gallot
Volunteer developer
Project scientist

Joined: 19 Aug 12
Posts: 644
ID: 164101
Credit: 305,010,093
RAC: 78 Message 130919 - Posted: 7 Jul 2019 | 13:31:15 UTC

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. Message 130943 - Posted: 8 Jul 2019 | 15:29:05 UTC

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

Message 130946 - Posted: 8 Jul 2019 | 16:45:32 UTC - in response to Message 130943.

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

Message 132732 - Posted: 9 Sep 2019 | 19:00:54 UTC

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

Message boards : Generalized Fermat Prime Search : GF prime gap size