Join PrimeGrid
Returning Participants
Community
Leader Boards
Results
Other
drummerslowrise

Message boards :
Proth Prime Search :
Can PPSMega be a Fermat Divisor?
Author 
Message 

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

CrunchiVolunteer tester
Send message
Joined: 25 Nov 09 Posts: 3114 ID: 50683 Credit: 76,797,694 RAC: 9,877

I know PPSE and PPS can be but is there some upper limit that would not make that possible for PPSMega?
https://www.primegrid.com/forum_forum.php?id=121
____________
92*10^^{1439761}1 NEARREPDIGIT PRIME :) :) :)
4 * 650^^{498101}1 CRUS PRIME
314187728^^{131072}+1 GENERALIZED FERMAT
Proud member of team Aggie The Pew. Go Aggie!  


I know PPSE and PPS can be but is there some upper limit that would not make that possible for PPSMega?
https://www.primegrid.com/forum_forum.php?id=121
Thank you. I'm aware of the Fermat Divisor Search. :)
However, my question still stands.  

Michael GoetzVolunteer moderator Project administrator
Send message
Joined: 21 Jan 10 Posts: 13804 ID: 53948 Credit: 345,369,032 RAC: 6,456

I know PPSE and PPS can be but is there some upper limit that would not make that possible for PPSMega?
Yes, but it's unlikely because of the high K that is currently being searched in PPSMEGA.
There are two known megaprime 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 PPSMEGA 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 75898^{524288}+1  


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 20140725, 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, PPSMEGA, or PPSDIV.
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 PPSDIV, because they have low k.
/JeppeSN  


Thank you for the info everyone!  


There are two known megaprime 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 FernandoProject administrator Volunteer tester Project scientist Send message
Joined: 21 Mar 19 Posts: 206 ID: 1108183 Credit: 11,958,242 RAC: 5,116

Yes. In fact the world record Fermat divisor before DIV was a PPSMega: 193*2^3329782+1.
It's less likely now, because PPSMega 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.  

BurVolunteer tester
Send message
Joined: 25 Feb 20 Posts: 511 ID: 1241833 Credit: 408,347,062 RAC: 23,798

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 = 5,700,000  

Ravi FernandoProject administrator Volunteer tester Project scientist Send message
Joined: 21 Mar 19 Posts: 206 ID: 1108183 Credit: 11,958,242 RAC: 5,116

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 lown, highk 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 GallotVolunteer developer Project scientist Send message
Joined: 19 Aug 12 Posts: 712 ID: 164101 Credit: 305,166,630 RAC: 0

(As an aside, the extremely lown, highk 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 F_{11}. :)
 


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  


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  

BurVolunteer tester
Send message
Joined: 25 Feb 20 Posts: 511 ID: 1241833 Credit: 408,347,062 RAC: 23,798

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 = 5,700,000  


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.  


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  

Message boards :
Proth Prime Search :
Can PPSMega be a Fermat Divisor? 