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: 553
ID: 164101
Credit: 304,715,793
RAC: 0
GFN Double Silver: Earned 200,000,000 credits (304,715,793)
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
Honorary cruncher
Avatar
Send message
Joined: 21 Jan 10
Posts: 13213
ID: 53948
Credit: 218,265,066
RAC: 12,106
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 Primes321 LLR Ruby: Earned 2,000,000 credits (2,822,730)Cullen LLR Ruby: Earned 2,000,000 credits (2,005,249)ESP LLR Turquoise: Earned 5,000,000 credits (5,009,577)Generalized Cullen/Woodall LLR Ruby: Earned 2,000,000 credits (2,145,754)PPS LLR Jade: Earned 10,000,000 credits (12,843,762)PSP LLR Turquoise: Earned 5,000,000 credits (5,197,957)SoB LLR Sapphire: Earned 20,000,000 credits (34,291,181)SR5 LLR Jade: Earned 10,000,000 credits (10,004,590)SGS LLR Ruby: Earned 2,000,000 credits (2,276,011)TRP LLR Ruby: Earned 2,000,000 credits (2,737,347)Woodall LLR Ruby: Earned 2,000,000 credits (2,195,123)321 Sieve Turquoise: Earned 5,000,000 credits (9,403,130)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 (20,114,159)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,114,260)GFN Emerald: Earned 50,000,000 credits (72,383,585)PSA Jade: Earned 10,000,000 credits (12,404,447)
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
(I am NOT an administrator anymore, so please don't PM me with questions. I can't help.)

Profile Crun-chiProject donor
Volunteer tester
Avatar
Send message
Joined: 25 Nov 09
Posts: 2886
ID: 50683
Credit: 55,710,613
RAC: 14,337
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 Primes321 LLR Silver: Earned 100,000 credits (229,492)Cullen LLR Silver: Earned 100,000 credits (110,733)PPS LLR Turquoise: Earned 5,000,000 credits (5,561,881)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,323,052)TRP LLR Silver: Earned 100,000 credits (122,712)Woodall LLR Silver: Earned 100,000 credits (122,944)321 Sieve 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,593,037)TRP Sieve (suspended) Silver: Earned 100,000 credits (255,612)AP 26/27 Ruby: Earned 2,000,000 credits (2,579,917)GFN Sapphire: Earned 20,000,000 credits (23,317,763)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?
____________
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 Gallot
Volunteer developer
Project scientist
Send message
Joined: 19 Aug 12
Posts: 553
ID: 164101
Credit: 304,715,793
RAC: 0
GFN Double Silver: Earned 200,000,000 credits (304,715,793)
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: 2886
ID: 50683
Credit: 55,710,613
RAC: 14,337
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 Primes321 LLR Silver: Earned 100,000 credits (229,492)Cullen LLR Silver: Earned 100,000 credits (110,733)PPS LLR Turquoise: Earned 5,000,000 credits (5,561,881)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,323,052)TRP LLR Silver: Earned 100,000 credits (122,712)Woodall LLR Silver: Earned 100,000 credits (122,944)321 Sieve 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,593,037)TRP Sieve (suspended) Silver: Earned 100,000 credits (255,612)AP 26/27 Ruby: Earned 2,000,000 credits (2,579,917)GFN Sapphire: Earned 20,000,000 credits (23,317,763)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 :)
____________
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 Gallot
Volunteer developer
Project scientist
Send message
Joined: 19 Aug 12
Posts: 553
ID: 164101
Credit: 304,715,793
RAC: 0
GFN Double Silver: Earned 200,000,000 credits (304,715,793)
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: 1124
ID: 306875
Credit: 13,832,702
RAC: 21,646
Found 1 prime in the 2020 Tour de Primes321 LLR Silver: Earned 100,000 credits (360,928)Cullen LLR Bronze: Earned 10,000 credits (98,851)ESP LLR Silver: Earned 100,000 credits (139,922)Generalized Cullen/Woodall LLR Bronze: Earned 10,000 credits (35,236)PPS LLR Ruby: Earned 2,000,000 credits (4,532,592)PSP LLR Silver: Earned 100,000 credits (212,242)SoB LLR Silver: Earned 100,000 credits (237,390)SR5 LLR Silver: Earned 100,000 credits (145,419)SGS LLR Bronze: Earned 10,000 credits (99,305)TRP LLR Bronze: Earned 10,000 credits (71,060)Woodall LLR Silver: Earned 100,000 credits (109,455)321 Sieve Silver: Earned 100,000 credits (175,037)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: 2886
ID: 50683
Credit: 55,710,613
RAC: 14,337
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 Primes321 LLR Silver: Earned 100,000 credits (229,492)Cullen LLR Silver: Earned 100,000 credits (110,733)PPS LLR Turquoise: Earned 5,000,000 credits (5,561,881)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,323,052)TRP LLR Silver: Earned 100,000 credits (122,712)Woodall LLR Silver: Earned 100,000 credits (122,944)321 Sieve 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,593,037)TRP Sieve (suspended) Silver: Earned 100,000 credits (255,612)AP 26/27 Ruby: Earned 2,000,000 credits (2,579,917)GFN Sapphire: Earned 20,000,000 credits (23,317,763)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) :)
____________
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!

Profile Michael GoetzProject donor
Honorary cruncher
Avatar
Send message
Joined: 21 Jan 10
Posts: 13213
ID: 53948
Credit: 218,265,066
RAC: 12,106
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 Primes321 LLR Ruby: Earned 2,000,000 credits (2,822,730)Cullen LLR Ruby: Earned 2,000,000 credits (2,005,249)ESP LLR Turquoise: Earned 5,000,000 credits (5,009,577)Generalized Cullen/Woodall LLR Ruby: Earned 2,000,000 credits (2,145,754)PPS LLR Jade: Earned 10,000,000 credits (12,843,762)PSP LLR Turquoise: Earned 5,000,000 credits (5,197,957)SoB LLR Sapphire: Earned 20,000,000 credits (34,291,181)SR5 LLR Jade: Earned 10,000,000 credits (10,004,590)SGS LLR Ruby: Earned 2,000,000 credits (2,276,011)TRP LLR Ruby: Earned 2,000,000 credits (2,737,347)Woodall LLR Ruby: Earned 2,000,000 credits (2,195,123)321 Sieve Turquoise: Earned 5,000,000 credits (9,403,130)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 (20,114,159)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,114,260)GFN Emerald: Earned 50,000,000 credits (72,383,585)PSA Jade: Earned 10,000,000 credits (12,404,447)
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
(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

[Return to PrimeGrid main page]
DNS Powered by DNSEXIT.COM
Copyright © 2005 - 2020 Rytis Slatkevičius (contact) and PrimeGrid community. Server load 2.79, 2.85, 3.16
Generated 31 May 2020 | 6:50:38 UTC