| Author |
Message |
|---|
|
|
|
Can these only be found via PPS LLR? |
|
|
 Michael Goetz Volunteer moderator
Project administrator
Send message
Joined: 21 Jan 10
Posts: 13804
ID: 53948
Credit: 345,369,032
RAC: 1,967
                              
|
Can these only be found via PPS LLR?
Any Proth number can be a Fermat divisor. (k * 2 ^ n + 1)
SGS no.
Woodall no.
GFN no.
321 some yes, some no.
TRP no.
GCW no.
SR5 no.
Cullen yes.
ESP yes.
PSP yes.
SoB yes.
PPSE yes
PPS yes
PPS-MEGA yes.
____________
My lucky number is 75898524288+1 |
|
|
|
|
|
Thank you Michael! |
|
|
Yves GallotVolunteer developer
Project scientist
Send message
Joined: 19 Aug 12
Posts: 712
ID: 164101
Credit: 305,166,630
RAC: 0
|
GFN no.
25 · 22141884 + 1 divides F2141872 and is a generalized Fermat number.
|
|
|
Michael GoetzVolunteer moderator
Project administrator
Send message
Joined: 21 Jan 10
Posts: 13804
ID: 53948
Credit: 345,369,032
RAC: 1,967
|
GFN no.
25 · 22141884 + 1 divides F2141872 and is a generalized Fermat number.
"GFN" meaning our GFN projects.
____________
My lucky number is 75898524288+1 |
|
|
|
|
Can these only be found via PPS LLR?
Any Proth number can be a Fermat divisor. (k * 2 ^ n + 1)
And if the number k*2^n + 1 is a divisor of a Fermat number, say F(m), then the index m satisfies:
m ≤ n-2
For generalized Fermat numbers GF(m, b) and xGF(m, b, a) we can only say
m ≤ n-1
Note that the number k*2^n + 1 is not necessarily a Proth number in the strict sense that 2^n > k. For example the four factors of F(10) = 2^1024 + 1 are:
11131*2^12 + 1
395937*2^14 + 1
1137640572563481089664199400165229051*2^12 + 1
15922836231138695035093355565980212884107486675001451682970617160257863311947248971452664548043591906237644522563833477152239872181860196421948439690685317315553051258143326480945577516888976026564843006895573500498133825643594092555886322403200003*2^13 + 1
and none of them are Proth primes in the strict sense.
/JeppeSN |
|
|
Yves GallotVolunteer developer
Project scientist
Send message
Joined: 19 Aug 12
Posts: 712
ID: 164101
Credit: 305,166,630
RAC: 0
|
GFN no.
25 · 22141884 + 1 divides F2141872 and is a generalized Fermat number.
"GFN" meaning our GFN projects.
A GFN can divide a Fermat number.
10590941048576 + 1 may be the largest known Fermat divisor (with a probability of (2/1059094)1048576).
|
|
|
|
|
GFN no.
25 · 22141884 + 1 divides F2141872 and is a generalized Fermat number.
"GFN" meaning our GFN projects.
Let me take a recent GFN16 project find as an example, namely the prime:
53942572^65536 + 1
To see this in the Proth form, we would need to split the base 53942572 into a power of two and an odd number. It goes like this 53942572 = 13485643*2^2 and so the GFN16 prime can be written:
13485643^65536*(2^2)^65536 + 1
or:
(13485643^65536)*2^131072 + 1
So this is of the "Proth" form k*2^n + 1 where n=131072 and k is the enormous odd number 13485643^65536. So given the form, it could divide some F(m) with m ≤ 131070. However, since k is so incredibly huge, there is no need of checking it, the chance is too slim.
If we found a GFN16 prime b^65536+1 with the special property that b is a really small odd number times a big power of two, the chances would be a little bit better. Say, if 25165824^65536+1 were prime (I have not checked, so it probably is not), then 25165824 = 3*2^23, and we would end up with "Proth" form:
3^65536*(2^23)^65536 + 1
or:
(3^65536)*2^1507328 + 1
but even in this extreme case, the size of k (= 3^65536) is so big that it is not worth the computation time to check if it is a Fermat divisor.
/JeppeSN
|
|
|
|
|
|
Similar remarks apply to GCW primes of the generalized Cullen form if the base is even, such as:
1323365*116^1323365 + 1 (Scott Brown, January 2018)
which could in principle be a Fermat divisor, but it is a waste of effort to check for it.
/JeppeSN |
|
|
|
|
|
Shorter put, I agree with Yves.
Note that his example 25*2^2141884 + 1 was found by "our" PPS LLR search, and was originally on the GFN Top 20.
/JeppeSN |
|
|
Yves GallotVolunteer developer
Project scientist
Send message
Joined: 19 Aug 12
Posts: 712
ID: 164101
Credit: 305,166,630
RAC: 0
|
|
Robish just asked me if there is a software he could use to check if 10590941048576 + 1 is the divisor of a Fermat number.
I was thinking of modifying genefer for this purpose but I think that we can do better.
If P is prime then 2P-1 = 1 (mod P).
But xn-1 = Prodd|n Phid(x), where Phid is the dth cyclotomic polynomial.
Then P = 10590941048576 + 1 divides at least one "cyclotomic number" Phid(2) where d is a divisor of 10590941048576.
Note that some of these numbers are some Fermat numbers.
b = 1059094 = 2 * 529547 then d = 2h * 529547k with 0 <= h, k <= 1048576.
We have Phid(x) = Phib(xd/b) and Phib(x) = Phib/2(-x).
Then we can compute the numbers Phid(2) modulo P and check if the result is zero.
This can be applied to 10223*231172165+1 or 3*210829346+1. They divide a huge cyclotomic number.
A small example: P = 64+1 is prime. P divides Phi648(2) = 2216 - 2108 + 1. (64 = 2 * 648)
|
|
|
robishVolunteer moderator
Volunteer tester
Send message
Joined: 7 Jan 12
Posts: 2139
ID: 126266
Credit: 6,807,374,603
RAC: 3,177,237
                   
|
Robish just asked me if there is a software he could use to check if 10590941048576 + 1 is the divisor of a Fermat number.
I was thinking of modifying genefer for this purpose but I think that we can do better.
If P is prime then 2P-1 = 1 (mod P).
But xn-1 = Prodd|n Phid(x), where Phid is the dth cyclotomic polynomial.
Then P = 10590941048576 + 1 divides at least one "cyclotomic number" Phid(2) where d is a divisor of 10590941048576.
Note that some of these numbers are some Fermat numbers.
b = 1059094 = 2 * 529547 then d = 2h * 529547k with 0 <= h, k <= 1048576.
We have Phid(x) = Phib(xd/b) and Phib(x) = Phib/2(-x).
Then we can compute the numbers Phid(2) modulo P and check if the result is zero.
This can be applied to 10223*231172165+1 or 3*210829346+1. They divide a huge cyclotomic number.
A small example: P = 64+1 is prime. P divides Phi648(2) = 2216 - 2108 + 1. (64 = 2 * 648)
Thanks Yves, but I fear that math is beyond me. I'll have to take your word for it :)
____________
My lucky numbers 10590941048576+1 and 224584605939537911+81292139*23#*n for n=0..26 |
|
|
Yves GallotVolunteer developer
Project scientist
Send message
Joined: 19 Aug 12
Posts: 712
ID: 164101
Credit: 305,166,630
RAC: 0
|
|
Actually, it is easier than I expected.
If p is an odd prime then p divides 2p-1 - 1 (Fermat's little theorem).
Let m be the smallest integer such that p divides 2m - 1 (the multiplicative order of 2 modulo p).
It's not difficult to prove that m must divide p-1 then if the factorisation of p-1 is known, m can be computed.
And we have the theorem:
If p doesn't divide m then
m is the order of a modulo p <=> p divides Phi_m(a) (the mth cyclotomic polynomial).
I can extend genefer with the computation of the multiplicative order of 2 modulo p = b^N+1.
If this order m is a power of 2 then the cyclotomic polynomial is of the form x^(m/2)+1 and p divides a Fermat number.
Otherwise p still divides Phi_m(2) which is also too large to be computed. |
|
|
