PrimeGrid
Please visit donation page to help the project cover running costs for this month

Toggle Menu

Join PrimeGrid

Returning Participants

Community

Leader Boards

Results

Other

drummers-lowrise

Advanced search

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

Author Message
Yves Gallot
Volunteer developer
Project scientist
Send message
Joined: 19 Aug 12
Posts: 672
ID: 164101
Credit: 305,042,960
RAC: 0
GFN Double Silver: Earned 200,000,000 credits (305,042,960)
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.

Profile Michael GoetzProject donor
Volunteer moderator
Project administrator
Avatar
Send message
Joined: 21 Jan 10
Posts: 13648
ID: 53948
Credit: 285,261,660
RAC: 53,155
The "Shut up already!" badge:  This loud mouth has mansplained on the forums over 10 thousand times!  Sheesh!!!Discovered the World's First GFN-19 prime!!!Discovered 1 mega primeFound 1 prime in the 2018 Tour de PrimesFound 1 prime in the 2019 Tour de PrimesFound 1 prime in the 2020 Tour de PrimesFound 2 primes in the 2021 Tour de Primes321 LLR Turquoise: Earned 5,000,000 credits (5,132,712)Cullen LLR Turquoise: Earned 5,000,000 credits (5,038,114)ESP LLR Turquoise: Earned 5,000,000 credits (6,177,890)Generalized Cullen/Woodall LLR Ruby: Earned 2,000,000 credits (2,258,477)PPS LLR Sapphire: Earned 20,000,000 credits (20,751,038)PSP LLR Turquoise: Earned 5,000,000 credits (7,956,186)SoB LLR Sapphire: Earned 20,000,000 credits (36,067,618)SR5 LLR Jade: Earned 10,000,000 credits (10,007,110)SGS LLR Ruby: Earned 2,000,000 credits (3,718,606)TRP LLR Turquoise: Earned 5,000,000 credits (5,084,329)Woodall LLR Turquoise: Earned 5,000,000 credits (5,007,789)321 Sieve (suspended) Jade: Earned 10,000,000 credits (10,061,196)Cullen/Woodall Sieve (suspended) Ruby: Earned 2,000,000 credits (4,170,256)Generalized Cullen/Woodall Sieve (suspended) Turquoise: Earned 5,000,000 credits (5,059,304)PPS Sieve Sapphire: Earned 20,000,000 credits (22,885,121)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Amethyst: Earned 1,000,000 credits (1,035,522)TRP Sieve (suspended) Ruby: Earned 2,000,000 credits (2,051,121)AP 26/27 Jade: Earned 10,000,000 credits (10,118,303)GFN Emerald: Earned 50,000,000 credits (78,031,938)WW Sapphire: Earned 20,000,000 credits (32,204,000)PSA Jade: Earned 10,000,000 credits (12,445,029)
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

Profile Crun-chiProject donor
Volunteer tester
Avatar
Send message
Joined: 25 Nov 09
Posts: 3070
ID: 50683
Credit: 63,378,402
RAC: 361
Eliminated 1 conjecture "k"Found 1 prime in the 2018 Tour de PrimesFound 1 prime in the 2019 Tour de PrimesFound 1 prime in the 2020 Tour de PrimesFound 1 prime in the 2021 Tour de Primes321 LLR Silver: Earned 100,000 credits (229,492)Cullen LLR Silver: Earned 100,000 credits (110,733)PPS LLR Jade: Earned 10,000,000 credits (11,335,374)PSP LLR Silver: Earned 100,000 credits (104,385)SoB LLR Silver: Earned 100,000 credits (106,117)SR5 LLR Silver: Earned 100,000 credits (139,802)SGS LLR Amethyst: Earned 1,000,000 credits (1,325,207)TRP LLR Gold: Earned 500,000 credits (626,755)Woodall LLR Silver: Earned 100,000 credits (122,944)321 Sieve (suspended) Silver: Earned 100,000 credits (104,900)Cullen/Woodall Sieve (suspended) Ruby: Earned 2,000,000 credits (2,000,599)Generalized Cullen/Woodall Sieve (suspended) Gold: Earned 500,000 credits (515,556)PPS Sieve Jade: Earned 10,000,000 credits (11,872,830)TRP Sieve (suspended) Silver: Earned 100,000 credits (255,612)AP 26/27 Ruby: Earned 2,000,000 credits (2,583,960)GFN Sapphire: Earned 20,000,000 credits (23,334,026)WW Amethyst: Earned 1,000,000 credits (1,088,000)PSA Turquoise: Earned 5,000,000 credits (7,522,050)
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 NEAR-REPDIGIT PRIME :) :) :)
4 * 650^498101-1 CRUS PRIME
314187728^131072+1 GENERALIZED FERMAT
Proud member of team Aggie The Pew. Go Aggie!

Yves Gallot
Volunteer developer
Project scientist
Send message
Joined: 19 Aug 12
Posts: 672
ID: 164101
Credit: 305,042,960
RAC: 0
GFN Double Silver: Earned 200,000,000 credits (305,042,960)
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.

Profile Crun-chiProject donor
Volunteer tester
Avatar
Send message
Joined: 25 Nov 09
Posts: 3070
ID: 50683
Credit: 63,378,402
RAC: 361
Eliminated 1 conjecture "k"Found 1 prime in the 2018 Tour de PrimesFound 1 prime in the 2019 Tour de PrimesFound 1 prime in the 2020 Tour de PrimesFound 1 prime in the 2021 Tour de Primes321 LLR Silver: Earned 100,000 credits (229,492)Cullen LLR Silver: Earned 100,000 credits (110,733)PPS LLR Jade: Earned 10,000,000 credits (11,335,374)PSP LLR Silver: Earned 100,000 credits (104,385)SoB LLR Silver: Earned 100,000 credits (106,117)SR5 LLR Silver: Earned 100,000 credits (139,802)SGS LLR Amethyst: Earned 1,000,000 credits (1,325,207)TRP LLR Gold: Earned 500,000 credits (626,755)Woodall LLR Silver: Earned 100,000 credits (122,944)321 Sieve (suspended) Silver: Earned 100,000 credits (104,900)Cullen/Woodall Sieve (suspended) Ruby: Earned 2,000,000 credits (2,000,599)Generalized Cullen/Woodall Sieve (suspended) Gold: Earned 500,000 credits (515,556)PPS Sieve Jade: Earned 10,000,000 credits (11,872,830)TRP Sieve (suspended) Silver: Earned 100,000 credits (255,612)AP 26/27 Ruby: Earned 2,000,000 credits (2,583,960)GFN Sapphire: Earned 20,000,000 credits (23,334,026)WW Amethyst: Earned 1,000,000 credits (1,088,000)PSA Turquoise: Earned 5,000,000 credits (7,522,050)
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 NEAR-REPDIGIT PRIME :) :) :)
4 * 650^498101-1 CRUS PRIME
314187728^131072+1 GENERALIZED FERMAT
Proud member of team Aggie The Pew. Go Aggie!

Yves Gallot
Volunteer developer
Project scientist
Send message
Joined: 19 Aug 12
Posts: 672
ID: 164101
Credit: 305,042,960
RAC: 0
GFN Double Silver: Earned 200,000,000 credits (305,042,960)
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.


Profile JeppeSNProject donor
Avatar
Send message
Joined: 5 Apr 14
Posts: 1533
ID: 306875
Credit: 35,610,008
RAC: 10,058
Found 1 prime in the 2020 Tour de Primes321 LLR Gold: Earned 500,000 credits (529,293)Cullen LLR Gold: Earned 500,000 credits (611,298)ESP LLR Silver: Earned 100,000 credits (174,818)Generalized Cullen/Woodall LLR Bronze: Earned 10,000 credits (35,236)PPS LLR Jade: Earned 10,000,000 credits (13,143,622)PSP LLR Silver: Earned 100,000 credits (428,457)SoB LLR Silver: Earned 100,000 credits (466,812)SR5 LLR Silver: Earned 100,000 credits (145,419)SGS LLR Silver: Earned 100,000 credits (112,277)TRP LLR Silver: Earned 100,000 credits (342,501)Woodall LLR Silver: Earned 100,000 credits (109,455)321 Sieve (suspended) Silver: Earned 100,000 credits (175,037)PPS Sieve Bronze: Earned 10,000 credits (10,113)AP 26/27 Bronze: Earned 10,000 credits (12,129)GFN Ruby: Earned 2,000,000 credits (2,059,478)WW Turquoise: Earned 5,000,000 credits (9,640,000)PSA Turquoise: Earned 5,000,000 credits (7,614,290)
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

Profile Crun-chiProject donor
Volunteer tester
Avatar
Send message
Joined: 25 Nov 09
Posts: 3070
ID: 50683
Credit: 63,378,402
RAC: 361
Eliminated 1 conjecture "k"Found 1 prime in the 2018 Tour de PrimesFound 1 prime in the 2019 Tour de PrimesFound 1 prime in the 2020 Tour de PrimesFound 1 prime in the 2021 Tour de Primes321 LLR Silver: Earned 100,000 credits (229,492)Cullen LLR Silver: Earned 100,000 credits (110,733)PPS LLR Jade: Earned 10,000,000 credits (11,335,374)PSP LLR Silver: Earned 100,000 credits (104,385)SoB LLR Silver: Earned 100,000 credits (106,117)SR5 LLR Silver: Earned 100,000 credits (139,802)SGS LLR Amethyst: Earned 1,000,000 credits (1,325,207)TRP LLR Gold: Earned 500,000 credits (626,755)Woodall LLR Silver: Earned 100,000 credits (122,944)321 Sieve (suspended) Silver: Earned 100,000 credits (104,900)Cullen/Woodall Sieve (suspended) Ruby: Earned 2,000,000 credits (2,000,599)Generalized Cullen/Woodall Sieve (suspended) Gold: Earned 500,000 credits (515,556)PPS Sieve Jade: Earned 10,000,000 credits (11,872,830)TRP Sieve (suspended) Silver: Earned 100,000 credits (255,612)AP 26/27 Ruby: Earned 2,000,000 credits (2,583,960)GFN Sapphire: Earned 20,000,000 credits (23,334,026)WW Amethyst: Earned 1,000,000 credits (1,088,000)PSA Turquoise: Earned 5,000,000 credits (7,522,050)
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 NEAR-REPDIGIT PRIME :) :) :)
4 * 650^498101-1 CRUS PRIME
314187728^131072+1 GENERALIZED FERMAT
Proud member of team Aggie The Pew. Go Aggie!

Profile Michael GoetzProject donor
Volunteer moderator
Project administrator
Avatar
Send message
Joined: 21 Jan 10
Posts: 13648
ID: 53948
Credit: 285,261,660
RAC: 53,155
The "Shut up already!" badge:  This loud mouth has mansplained on the forums over 10 thousand times!  Sheesh!!!Discovered the World's First GFN-19 prime!!!Discovered 1 mega primeFound 1 prime in the 2018 Tour de PrimesFound 1 prime in the 2019 Tour de PrimesFound 1 prime in the 2020 Tour de PrimesFound 2 primes in the 2021 Tour de Primes321 LLR Turquoise: Earned 5,000,000 credits (5,132,712)Cullen LLR Turquoise: Earned 5,000,000 credits (5,038,114)ESP LLR Turquoise: Earned 5,000,000 credits (6,177,890)Generalized Cullen/Woodall LLR Ruby: Earned 2,000,000 credits (2,258,477)PPS LLR Sapphire: Earned 20,000,000 credits (20,751,038)PSP LLR Turquoise: Earned 5,000,000 credits (7,956,186)SoB LLR Sapphire: Earned 20,000,000 credits (36,067,618)SR5 LLR Jade: Earned 10,000,000 credits (10,007,110)SGS LLR Ruby: Earned 2,000,000 credits (3,718,606)TRP LLR Turquoise: Earned 5,000,000 credits (5,084,329)Woodall LLR Turquoise: Earned 5,000,000 credits (5,007,789)321 Sieve (suspended) Jade: Earned 10,000,000 credits (10,061,196)Cullen/Woodall Sieve (suspended) Ruby: Earned 2,000,000 credits (4,170,256)Generalized Cullen/Woodall Sieve (suspended) Turquoise: Earned 5,000,000 credits (5,059,304)PPS Sieve Sapphire: Earned 20,000,000 credits (22,885,121)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Amethyst: Earned 1,000,000 credits (1,035,522)TRP Sieve (suspended) Ruby: Earned 2,000,000 credits (2,051,121)AP 26/27 Jade: Earned 10,000,000 credits (10,118,303)GFN Emerald: Earned 50,000,000 credits (78,031,938)WW Sapphire: Earned 20,000,000 credits (32,204,000)PSA Jade: Earned 10,000,000 credits (12,445,029)
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

[Return to PrimeGrid main page]
DNS Powered by DNSEXIT.COM
Copyright © 2005 - 2021 Rytis Slatkevičius (contact) and PrimeGrid community. Server load 4.48, 3.82, 3.10
Generated 18 Sep 2021 | 20:30:27 UTC