| Author |
Message |
|---|
|
|
|
I know PPSE and PPS can be but is there some upper limit that would not make that possible for PPS-Mega? |
|
|
|
|
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 REPDIGIT PRIME :) :) :)
314187728^131072+1 GENERALIZED FERMAT
31*332^367560+1 CRUS PRIME
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 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. |
|
|
 Michael Goetz Volunteer moderator
Project administrator
Send message
Joined: 21 Jan 10
Posts: 13513
ID: 53948
Credit: 236,922,854
RAC: 0
                           
|
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 |
|
|
|
|
|
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 |
|
|
|
|
|
Thank you for the info everyone! |
|
|
|
|
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 FernandoProject administrator
Volunteer tester
Project scientist
Send message
Joined: 21 Mar 19
Posts: 144
ID: 1108183
Credit: 8,505,009
RAC: 0
             
|
|
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. |
|
|
BurVolunteer tester
Send message
Joined: 25 Feb 20
Posts: 332
ID: 1241833
Credit: 22,611,276
RAC: 0
              
|
|
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?
____________
Primes: 1281979 & 12+8+1979 & 1+2+8+1+9+7+9 & 1^2+2^2+8^2+1^2+9^2+7^2+9^2 & 12*8+19*79 & 12^8-1979 & 1281979 + 4 (cousin prime) |
|
|
Ravi FernandoProject administrator
Volunteer tester
Project scientist
Send message
Joined: 21 Mar 19
Posts: 144
ID: 1108183
Credit: 8,505,009
RAC: 0
|
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 GallotVolunteer developer
Project scientist
Send message
Joined: 19 Aug 12
Posts: 644
ID: 164101
Credit: 305,010,093
RAC: 0
|
(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. :-)
|
|
|
|
|
|
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 |
|
|
