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 : Proth Prime Search : Can PPS-Mega be a Fermat Divisor?

Author Message
Profile Jordan Romaidis
Avatar
Send message
Joined: 11 May 17
Posts: 255
ID: 880615
Credit: 709,039,252
RAC: 167,140
Discovered 4 mega primesEliminated 1 conjecture "k"Discovered 1 AP26Found 1 prime in the 2018 Tour de PrimesFound 2 primes in the 2019 Tour de PrimesFound 2 primes in the 2020 Tour de PrimesFound 1 mega prime in the 2020 Tour de PrimesFound 1 prime in the 2020 Tour de Primes Mountain StageFound 1 mega prime in the 2020 Tour de Primes Mountain StageFound 1 prime in the 2021 Tour de Primes321 LLR Turquoise: Earned 5,000,000 credits (5,014,730)Cullen LLR Ruby: Earned 2,000,000 credits (2,080,460)ESP LLR Gold: Earned 500,000 credits (502,799)Generalized Cullen/Woodall LLR Turquoise: Earned 5,000,000 credits (6,000,054)PPS LLR Emerald: Earned 50,000,000 credits (98,884,636)PSP LLR Amethyst: Earned 1,000,000 credits (1,092,773)SoB LLR Sapphire: Earned 20,000,000 credits (40,278,369)SR5 LLR Jade: Earned 10,000,000 credits (17,734,011)SGS LLR Jade: Earned 10,000,000 credits (19,234,100)TRP LLR Gold: Earned 500,000 credits (691,677)Woodall LLR Jade: Earned 10,000,000 credits (15,028,246)321 Sieve (suspended) Amethyst: Earned 1,000,000 credits (1,084,376)Generalized Cullen/Woodall Sieve (suspended) Sapphire: Earned 20,000,000 credits (20,606,749)PPS Sieve Sapphire: Earned 20,000,000 credits (23,323,949)AP 26/27 Double Silver: Earned 200,000,000 credits (238,387,409)GFN Double Bronze: Earned 100,000,000 credits (151,779,252)WW Jade: Earned 10,000,000 credits (14,304,000)PSA Emerald: Earned 50,000,000 credits (53,011,665)
Message 146713 - Posted: 16 Dec 2020 | 20:55:46 UTC

I know PPSE and PPS can be but is there some upper limit that would not make that possible for PPS-Mega?

Profile Crun-chiProject donor
Volunteer tester
Avatar
Send message
Joined: 25 Nov 09
Posts: 3070
ID: 50683
Credit: 63,378,402
RAC: 268
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 146716 - Posted: 16 Dec 2020 | 21:39:25 UTC - in response to Message 146713.

I know PPSE and PPS can be but is there some upper limit that would not make that possible for PPS-Mega?


https://www.primegrid.com/forum_forum.php?id=121
____________
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 Jordan Romaidis
Avatar
Send message
Joined: 11 May 17
Posts: 255
ID: 880615
Credit: 709,039,252
RAC: 167,140
Discovered 4 mega primesEliminated 1 conjecture "k"Discovered 1 AP26Found 1 prime in the 2018 Tour de PrimesFound 2 primes in the 2019 Tour de PrimesFound 2 primes in the 2020 Tour de PrimesFound 1 mega prime in the 2020 Tour de PrimesFound 1 prime in the 2020 Tour de Primes Mountain StageFound 1 mega prime in the 2020 Tour de Primes Mountain StageFound 1 prime in the 2021 Tour de Primes321 LLR Turquoise: Earned 5,000,000 credits (5,014,730)Cullen LLR Ruby: Earned 2,000,000 credits (2,080,460)ESP LLR Gold: Earned 500,000 credits (502,799)Generalized Cullen/Woodall LLR Turquoise: Earned 5,000,000 credits (6,000,054)PPS LLR Emerald: Earned 50,000,000 credits (98,884,636)PSP LLR Amethyst: Earned 1,000,000 credits (1,092,773)SoB LLR Sapphire: Earned 20,000,000 credits (40,278,369)SR5 LLR Jade: Earned 10,000,000 credits (17,734,011)SGS LLR Jade: Earned 10,000,000 credits (19,234,100)TRP LLR Gold: Earned 500,000 credits (691,677)Woodall LLR Jade: Earned 10,000,000 credits (15,028,246)321 Sieve (suspended) Amethyst: Earned 1,000,000 credits (1,084,376)Generalized Cullen/Woodall Sieve (suspended) Sapphire: Earned 20,000,000 credits (20,606,749)PPS Sieve Sapphire: Earned 20,000,000 credits (23,323,949)AP 26/27 Double Silver: Earned 200,000,000 credits (238,387,409)GFN Double Bronze: Earned 100,000,000 credits (151,779,252)WW Jade: Earned 10,000,000 credits (14,304,000)PSA Emerald: Earned 50,000,000 credits (53,011,665)
Message 146720 - Posted: 16 Dec 2020 | 21:57:21 UTC - in response to Message 146716.

I know PPSE and PPS can be but is there some upper limit that would not make that possible for PPS-Mega?


https://www.primegrid.com/forum_forum.php?id=121


Thank you. I'm aware of the Fermat Divisor Search. :)

However, my question still stands.

Profile Michael GoetzProject donor
Volunteer moderator
Project administrator
Avatar
Send message
Joined: 21 Jan 10
Posts: 13648
ID: 53948
Credit: 285,351,178
RAC: 47,109
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,322,963)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,032,821)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 146721 - Posted: 16 Dec 2020 | 22:03:47 UTC - in response to Message 146713.
Last modified: 16 Dec 2020 | 22:05:19 UTC

I know PPSE and PPS can be but is there some upper limit that would not make that possible for PPS-Mega?


Yes, but it's unlikely because of the high K that is currently being searched in PPS-MEGA.

There are two known mega-prime Fermat divisors (I think it's just two), and PrimeGrid found both of them. The most recent one was found on the Fermat Divisor search, but it's still a Proth prime and theoretically could have been found in the PPS or or PPS MEGA projects.

The first one, found in 2014, actually was found on our PPS-MEGA prime search.

https://www.primegrid.com/primes/primes.php?project=MEGA&factors=F&only=ONLY&announcements=ANNOUNCEMENTS&sortby=size&dc=no
____________
My lucky number is 75898524288+1

Profile JeppeSNProject donor
Avatar
Send message
Joined: 5 Apr 14
Posts: 1533
ID: 306875
Credit: 35,634,818
RAC: 9,614
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,168,206)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 146722 - Posted: 16 Dec 2020 | 22:06:45 UTC

Sure they can, and it has happened. Search with https://www.primegrid.com/primes/primes.php?project=MEG&factors=XGF&only=ONLY&sortby=date; on 2014-07-25, you see:

193*2^3329782+1 is a Factor of F3329780!!!! (13086.930000 seconds)


The probability a Proth prime k*2^n + 1 divides a Fermat number, is 1/k. It does not matter if it is a megaprime or not, or if it comes from PPS, PPSE, PPS-MEGA, or PPS-DIV.

In 2014, MEGA worked on candidates with k < 1200. For the time being, MEGA is working on 1200 < k < 10000. So statistically, you need thousands of these primes before you have a Fermat divisor. But you can still be lucky.

The highest chances, you get with 321 and PPS-DIV, because they have low k.

/JeppeSN

Profile Jordan Romaidis
Avatar
Send message
Joined: 11 May 17
Posts: 255
ID: 880615
Credit: 709,039,252
RAC: 167,140
Discovered 4 mega primesEliminated 1 conjecture "k"Discovered 1 AP26Found 1 prime in the 2018 Tour de PrimesFound 2 primes in the 2019 Tour de PrimesFound 2 primes in the 2020 Tour de PrimesFound 1 mega prime in the 2020 Tour de PrimesFound 1 prime in the 2020 Tour de Primes Mountain StageFound 1 mega prime in the 2020 Tour de Primes Mountain StageFound 1 prime in the 2021 Tour de Primes321 LLR Turquoise: Earned 5,000,000 credits (5,014,730)Cullen LLR Ruby: Earned 2,000,000 credits (2,080,460)ESP LLR Gold: Earned 500,000 credits (502,799)Generalized Cullen/Woodall LLR Turquoise: Earned 5,000,000 credits (6,000,054)PPS LLR Emerald: Earned 50,000,000 credits (98,884,636)PSP LLR Amethyst: Earned 1,000,000 credits (1,092,773)SoB LLR Sapphire: Earned 20,000,000 credits (40,278,369)SR5 LLR Jade: Earned 10,000,000 credits (17,734,011)SGS LLR Jade: Earned 10,000,000 credits (19,234,100)TRP LLR Gold: Earned 500,000 credits (691,677)Woodall LLR Jade: Earned 10,000,000 credits (15,028,246)321 Sieve (suspended) Amethyst: Earned 1,000,000 credits (1,084,376)Generalized Cullen/Woodall Sieve (suspended) Sapphire: Earned 20,000,000 credits (20,606,749)PPS Sieve Sapphire: Earned 20,000,000 credits (23,323,949)AP 26/27 Double Silver: Earned 200,000,000 credits (238,387,409)GFN Double Bronze: Earned 100,000,000 credits (151,779,252)WW Jade: Earned 10,000,000 credits (14,304,000)PSA Emerald: Earned 50,000,000 credits (53,011,665)
Message 146723 - Posted: 16 Dec 2020 | 22:10:28 UTC

Thank you for the info everyone!

Profile JeppeSNProject donor
Avatar
Send message
Joined: 5 Apr 14
Posts: 1533
ID: 306875
Credit: 35,634,818
RAC: 9,614
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,168,206)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 146724 - Posted: 16 Dec 2020 | 22:13:09 UTC - in response to Message 146721.

There are two known mega-prime Fermat divisors (I think it's just two)


I did not see your answer before I wrote mine, so I repeat a lot of what you said.

It is actually three megaprime Fermat divisors now, since Ryan Propper's record this October; see Fermat Divisors Top Twenty.

/JeppeSN

Ravi Fernando
Project administrator
Volunteer tester
Project scientist
Send message
Joined: 21 Mar 19
Posts: 176
ID: 1108183
Credit: 10,207,198
RAC: 5,098
321 LLR Gold: Earned 500,000 credits (591,844)Cullen LLR Bronze: Earned 10,000 credits (82,217)ESP LLR Bronze: Earned 10,000 credits (16,570)Generalized Cullen/Woodall LLR Bronze: Earned 10,000 credits (12,551)PPS LLR Ruby: Earned 2,000,000 credits (3,098,521)PSP LLR Silver: Earned 100,000 credits (106,263)SoB LLR Silver: Earned 100,000 credits (258,849)SR5 LLR Bronze: Earned 10,000 credits (59,499)SGS LLR Silver: Earned 100,000 credits (148,878)TRP LLR Silver: Earned 100,000 credits (195,905)Woodall LLR Bronze: Earned 10,000 credits (40,424)321 Sieve (suspended) Turquoise: Earned 5,000,000 credits (5,001,667)AP 26/27 Bronze: Earned 10,000 credits (72,774)GFN Gold: Earned 500,000 credits (502,872)WW Bronze: Earned 10,000 credits (12,000)
Message 146726 - Posted: 16 Dec 2020 | 22:31:02 UTC
Last modified: 16 Dec 2020 | 22:32:17 UTC

Yes. In fact the world record Fermat divisor before DIV was a PPS-Mega: 193*2^3329782+1.

It's less likely now, because PPS-Mega is searching 1200<k<10000 instead of k<1200, but it's still certainly possible. (Rule of thumb: if k*2^n+1 is prime where k is odd, it has a 1/k chance of being a Fermat divisor. There are rare examples of k's that break this rule, meaning they have either a better chance or no chance at all.) For what it's worth, I think DIV, PPS, PPSE, and 321 are currently all better bets.

Edit: oh wow, I'm slow.

Profile BurProject donor
Volunteer tester
Avatar
Send message
Joined: 25 Feb 20
Posts: 462
ID: 1241833
Credit: 279,927,511
RAC: 549,978
321 LLR Ruby: Earned 2,000,000 credits (2,092,823)Cullen LLR Ruby: Earned 2,000,000 credits (2,002,841)ESP LLR Amethyst: Earned 1,000,000 credits (1,445,099)Generalized Cullen/Woodall LLR Ruby: Earned 2,000,000 credits (2,180,764)PPS LLR Amethyst: Earned 1,000,000 credits (1,225,852)PSP LLR Ruby: Earned 2,000,000 credits (2,064,832)SoB LLR Amethyst: Earned 1,000,000 credits (1,669,219)SR5 LLR Ruby: Earned 2,000,000 credits (2,065,004)SGS LLR Amethyst: Earned 1,000,000 credits (1,202,156)TRP LLR Ruby: Earned 2,000,000 credits (2,089,856)Woodall LLR Ruby: Earned 2,000,000 credits (2,112,258)321 Sieve (suspended) Ruby: Earned 2,000,000 credits (2,107,153)PPS Sieve Turquoise: Earned 5,000,000 credits (5,080,097)AP 26/27 Ruby: Earned 2,000,000 credits (4,685,837)GFN Turquoise: Earned 5,000,000 credits (7,489,336)WW Double Silver: Earned 200,000,000 credits (239,400,000)PSA Amethyst: Earned 1,000,000 credits (1,022,470)
Message 146750 - Posted: 17 Dec 2020 | 18:19:03 UTC

There are Fermat divisors whose existence seem greatly improbable, yet here they are:

1527888802614951 · 2120 + 1 divides F118
15249465809 · 22591 + 1 divides F2587

There are more with large k: Fermat factors

Or is that 1/k conjectured probability not true for small n?
____________
1281979 * 2^485014 + 1 is prime ... no further hits up to: n = 4,800,000

Ravi Fernando
Project administrator
Volunteer tester
Project scientist
Send message
Joined: 21 Mar 19
Posts: 176
ID: 1108183
Credit: 10,207,198
RAC: 5,098
321 LLR Gold: Earned 500,000 credits (591,844)Cullen LLR Bronze: Earned 10,000 credits (82,217)ESP LLR Bronze: Earned 10,000 credits (16,570)Generalized Cullen/Woodall LLR Bronze: Earned 10,000 credits (12,551)PPS LLR Ruby: Earned 2,000,000 credits (3,098,521)PSP LLR Silver: Earned 100,000 credits (106,263)SoB LLR Silver: Earned 100,000 credits (258,849)SR5 LLR Bronze: Earned 10,000 credits (59,499)SGS LLR Silver: Earned 100,000 credits (148,878)TRP LLR Silver: Earned 100,000 credits (195,905)Woodall LLR Bronze: Earned 10,000 credits (40,424)321 Sieve (suspended) Turquoise: Earned 5,000,000 credits (5,001,667)AP 26/27 Bronze: Earned 10,000 credits (72,774)GFN Gold: Earned 500,000 credits (502,872)WW Bronze: Earned 10,000 credits (12,000)
Message 146753 - Posted: 17 Dec 2020 | 18:57:47 UTC - in response to Message 146750.

There are Fermat divisors whose existence seem greatly improbable, yet here they are:

1527888802614951 · 2120 + 1 divides F118
15249465809 · 22591 + 1 divides F2587

There are more with large k: Fermat factors

Or is that 1/k conjectured probability not true for small n?

The 1/k heuristic is fine in these cases; it's just that people have searched many billions of candidates, and a very large number of very small probabilities adds up to a reasonable probability. It's important here that the factors you're referring to are only tens to hundreds of digits long, so they can be tested millions of times faster than megaprimes.

(As an aside, the extremely low-n, high-k end of the FermatSearch spectrum doesn't even search one candidate at a time; they literally expand out the Fermat number and try to factor it with the elliptic curve method. That's how we know some Fermat divisors where k has ~50 digits.)

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 146762 - Posted: 17 Dec 2020 | 23:13:31 UTC - in response to Message 146753.

(As an aside, the extremely low-n, high-k end of the FermatSearch spectrum doesn't even search one candidate at a time; they literally expand out the Fermat number and try to factor it with the elliptic curve method. That's how we know some Fermat divisors where k has ~50 digits.)

And we know a Fermat divisor where k has > 500 digits, the largest prime factor of F11. :-)

Profile JeppeSNProject donor
Avatar
Send message
Joined: 5 Apr 14
Posts: 1533
ID: 306875
Credit: 35,634,818
RAC: 9,614
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,168,206)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 146782 - Posted: 18 Dec 2020 | 9:20:25 UTC - in response to Message 146762.

Exactly. It is very plausible that the 1/k heuristic will hold.

But you should not think that the factors of Fermat numbers will typically have low k. We can post the factors of F11 just to illustrate:

39*2^13 + 1 119*2^13 + 1 10253207784531279*2^14 + 1 434673084282938711*2^13 + 1 21174615134173285574982784529334689743337627529744150958172243537764108788193250592967656046192485007078101912652776662834559689734635521223667093019353364100169585433799507320937371688159076970887037493581569352118776521064958422163933812649044026502558555356775560067461648993426750049061580191794744396103493131476781686200989377719638682976424873973574085951980316371376859104992795318729984801869785145588809492038969317284320651500418425949345494944448110057412733268967446592534704415768023768439849177511907048426136846561848711377379319145718177075053*2^13 + 1

Only the first two factors (Cunningham 1899) are Proth primes (with 2^n > k).

/JeppeSN

Profile JeppeSNProject donor
Avatar
Send message
Joined: 5 Apr 14
Posts: 1533
ID: 306875
Credit: 35,634,818
RAC: 9,614
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,168,206)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 146783 - Posted: 18 Dec 2020 | 9:30:28 UTC - in response to Message 146782.

Fermat numbers F6, F7, F8, F10, F13, F14, F17, F20, F22 etc. have no prime factors that are Proth primes. I wonder how often that will happen "in the long run" (asymptotically). /JeppeSN

Profile BurProject donor
Volunteer tester
Avatar
Send message
Joined: 25 Feb 20
Posts: 462
ID: 1241833
Credit: 279,927,511
RAC: 549,978
321 LLR Ruby: Earned 2,000,000 credits (2,092,823)Cullen LLR Ruby: Earned 2,000,000 credits (2,002,841)ESP LLR Amethyst: Earned 1,000,000 credits (1,445,099)Generalized Cullen/Woodall LLR Ruby: Earned 2,000,000 credits (2,180,764)PPS LLR Amethyst: Earned 1,000,000 credits (1,225,852)PSP LLR Ruby: Earned 2,000,000 credits (2,064,832)SoB LLR Amethyst: Earned 1,000,000 credits (1,669,219)SR5 LLR Ruby: Earned 2,000,000 credits (2,065,004)SGS LLR Amethyst: Earned 1,000,000 credits (1,202,156)TRP LLR Ruby: Earned 2,000,000 credits (2,089,856)Woodall LLR Ruby: Earned 2,000,000 credits (2,112,258)321 Sieve (suspended) Ruby: Earned 2,000,000 credits (2,107,153)PPS Sieve Turquoise: Earned 5,000,000 credits (5,080,097)AP 26/27 Ruby: Earned 2,000,000 credits (4,685,837)GFN Turquoise: Earned 5,000,000 credits (7,489,336)WW Double Silver: Earned 200,000,000 credits (239,400,000)PSA Amethyst: Earned 1,000,000 credits (1,022,470)
Message 150675 - Posted: 19 Jun 2021 | 6:27:30 UTC - in response to Message 146783.

I thought about this again recently and for the small Fermat numbers, isn't it even more likely for their factors aren't Proth primes?

After all the 2^n is comparatively small and unless the Fermat number has a lot of factors, k has to be large to make up for it. I always forget the heuristics for the amount of prime factors a number has, but I think the average k could be calculated from that for each Fermat number?
____________
1281979 * 2^485014 + 1 is prime ... no further hits up to: n = 4,800,000

Profile JeppeSNProject donor
Avatar
Send message
Joined: 5 Apr 14
Posts: 1533
ID: 306875
Credit: 35,634,818
RAC: 9,614
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,168,206)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 150677 - Posted: 19 Jun 2021 | 14:08:43 UTC - in response to Message 150675.
Last modified: 19 Jun 2021 | 14:58:31 UTC

Yeah, most of the prime factors of a Fermat number will not be Proth primes because the odd k will be much much larger than the power of two it is multiplied by.

We can take F11 as an example. Its prime factors are:

39*2^13 + 1 119*2^13 + 1 10253207784531279*2^14 + 1 434673084282938711*2^13 + 1 21174615134173285574982784529334689743337627529744150958172243537764108788193250592967656046192485007078101912652776662834559689734635521223667093019353364100169585433799507320937371688159076970887037493581569352118776521064958422163933812649044026502558555356775560067461648993426750049061580191794744396103493131476781686200989377719638682976424873973574085951980316371376859104992795318729984801869785145588809492038969317284320651500418425949345494944448110057412733268967446592534704415768023768439849177511907048426136846561848711377379319145718177075053*2^13 + 1

This one has two lucky (by which I mean very small) factors. These two are Proth primes. The remaining ones are not.

For larger Fermat numbers, it is not unusual that none of the prime factors are Proth primes, I think. That happens for m = 6, 7, 8, 10, 13, 14, 17, ...

/JeppeSN

EDIT: Wauw, this is exactly the same I wrote back in December, in the same thread.

Profile JeppeSNProject donor
Avatar
Send message
Joined: 5 Apr 14
Posts: 1533
ID: 306875
Credit: 35,634,818
RAC: 9,614
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,168,206)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 150678 - Posted: 19 Jun 2021 | 14:54:57 UTC - in response to Message 150677.

The one known factor of Fermat number F28 is a bit interesting.

If you write it with 2^30 in it (where exponent 30 = 28+2 is taken because of Lucas's result on the form of Fermat divisors), then it is:

1645396439872*2^30 + 1
and since 1645396439872 > 2^30, a too naive search could lead you to the false conclusion that no Proth prime divisors of F28 exist.

However, if you rewrite the same factor so that k becomes odd, then it looks like:
25709319373*2^36 + 1
and because 25709319373 < 2^36, we see that this is a Proth prime.

Based on this, what is the highest m for which we can rigorously prove that no divisor of F_m is a Proth prime (after rewriting that divisor with odd k)?

/JeppeSN

Post to thread

Message boards : Proth Prime Search : Can PPS-Mega be a Fermat Divisor?

[Return to PrimeGrid main page]
DNS Powered by DNSEXIT.COM
Copyright © 2005 - 2021 Rytis Slatkevičius (contact) and PrimeGrid community. Server load 1.31, 1.51, 1.70
Generated 21 Sep 2021 | 19:48:38 UTC