Join PrimeGrid
Returning Participants
Community
Leader Boards
Results
Other
drummerslowrise

Message boards :
Fermat Divisor Search :
What primes can be Fermat divisors?
Author 
Message 
Ravi FernandoProject administrator Volunteer tester Project scientist Send message
Joined: 21 Mar 19 Posts: 205 ID: 1108183 Credit: 11,571,173 RAC: 4,503

Some people have been asking why PPSDIV is testing the numbers it is, so I thought I'd take a moment to explain what primes can be Fermat divisors, and with what probability we expect them to be.
The short answer: Every prime has the form p = k*2^n + 1 for some odd number k and some n >= 0. If you write a prime in this form, it usually has a 1/k chance of dividing some Fermat number. (Of course every prime either divides a Fermat number or doesn't, so this really only makes sense when you fix k and look at many primes.) So the rough guideline is that smaller k's are better, and n doesn't matter once you've found a prime.
But in 1906, J.C. Morehead discovered that this isn't always correct: 3*2^n + 1 can't divide a Fermat number if n is even. In the 1970s and '80s, both Solomon Golomb and Hiromi Suyama noticed that the same is true if 3 is replaced by 3d^2, provided that d is not divisible by 3. So some (k, n) combinations don't need to be searched.
Recently, inspired by this thread and messages with Yves Gallot and JeppeSN, I found some other cases that can't produce Fermat divisors. Any (k, n) pair of the following types can be ruled out:
1) k = 3d^2, d not divisible by 3, and n even (Morehead, Golomb, Suyama)
2) k = 27d^6, d not divisible by 3, and n even
3) k = 9d^4, d not divisible by 3, and n ≡ 2 mod 4
4) k = 729d^12, d not divisible by 3, and n ≡ 2 mod 4
In the last two cases, if d is also not divisible by 5, then the candidates with n ≡ 0 mod 4 are sieved out by the prime 5. So for all of these values of k (including 3, 9, 27, and 729), it's still true that p = k*2^n + 1 can't be a Fermat divisor when n is even. I've looked for other k's like this without any success. (In case you're wondering whether it's true for all powers of 3: it's false for 243, and I strongly suspect it's false for others too.)
The ideas that go into the proofs also point to some cases that are more likely than usual to produce Fermat divisors. Primes with k and n as follows should have more than a 1/k chance of being Fermat divisors, except when they also fall into the excluded cases above:
5) k = an mth power that is divisible by m, for some odd number m, and any n
6) k = 3d^2, 27d^6, 9d^4, or 729d^12, and n as before, but where d *is* divisible by 3
For each case, I have a prediction of the chance that p is a Fermat divisor. Essentially, case (5) multiplies the probability by m, and case (6) multiplies it by 3. Other than cases (16), my best guess is that the 1/k heuristic is correct.
After I made these predictions, it became clear that k = 3^9 = 19683 was unusually promising. Since it's a 9th power that is divisible by 9, case (5) gives it a 9/k chance of producing Fermat divisors, instead of the usual 1/k. But it also equals 27d^6 with d=3, so case (6) applies if n is even. The result is that when n is even, primes of the form 3^9 * 2^n + 1 should have a 1/729 chance of being Fermat divisors27 times better than usual! Better yet, PrimeGrid has never tested this k before, so there should be lots of undiscovered primes out there with reasonably small n. This is why we're starting the Fermat divisor search with k=19683.
Once we've tested k=19683 to a reasonable n level, we'll move over to small k's, specifically 5<=k<=49. These have much better chances of producing Fermat divisors, and they haven't been tested to their full potential. There are three special cases in this k range: k=9 and 27 can't produce Fermat divisors with n even, and k=27 should have a 1/9 chance with n odd, because of case (5). So we'll skip the even n's with k=9 and 27. For k=27 and n odd, we will doublecheck the relevant work that's been done on PRPNet.  


That is excellent work, Ravi Fernando.
I wonder if you are the first person to notice these facts (apart from (1) which we know was proved earlier).
One thing is how "probable" one particular prime is to divide a Fermat number. Another thing how frequently primes (Fermat divisors or not) appear in each k sequence. I hope I am making sense. If a k value produced many primes (compared to "usual" k values) and had a high "probability" of being a Fermat divisor per prime, that would be doubly attractive.
/JeppeSN  

Ravi FernandoProject administrator Volunteer tester Project scientist Send message
Joined: 21 Mar 19 Posts: 205 ID: 1108183 Credit: 11,571,173 RAC: 4,503

One thing is how "probable" one particular prime is to divide a Fermat number. Another thing how frequently primes (Fermat divisors or not) appear in each k sequence. I hope I am making sense. If a k value produced many primes (compared to "usual" k values) and had a high "probability" of being a Fermat divisor per prime, that would be doubly attractive.
Right, some k's do produce more primes than others. But this seems to be entirely explained by sieving (and algebraic factorizations for some k). Once we've sieved appropriately, I know of no reason that any candidate is more or less likely to be prime than any other candidate of the same size.
For example: there are 80 known primes with k=39, and only three with k=47. This is mostly because almost every 47*2^n+1 is divisible by a prime less than 15, and almost no 39*2^n+1 is. We'll almost certainly find more k=39 primes than k=47 primes in this project. But it will take proportionally more LLR tests to find them.  


Right, some k's do produce more primes than others. But this seems to be entirely explained by sieving (and algebraic factorizations for some k). Once we've sieved appropriately, I know of no reason that any candidate is more or less likely to be prime than any other candidate of the same size.
I understand, you are right. So, after sieving, every task (of a given size) has the same probability of being prime.
It would still be nice if the "heavy k" where many candidates survive sieving and much work must be done, were also the k with attractive Fermat divisor perspectives.
/JeppeSN  


Generalized Fermat prime dividing Fermat number
A generalized Fermat prime is a prime of the form GF(m,b) = b^(2^m) + 1 with m≥1. Equivalently, by taking x=b^(2^{m1}), a generalized Fermat prime is just a prime of form x^2 + 1, or "a nearsquare prime".
The fourth of Landau's problems (1912) asks if there are infinitely many primes of that type.
A nearsquare prime can be a Fermat divisor. (At least) Two examples are known:
13^2 * 2^63686 + 1 divides F63679 (Dubner & Gallot 1998)
5^2 * 2^2141884 divides F2141872 (PrimeGrid 2011)
Whenever we find a Fermat divisor where k is an odd square not divisible by 3, then n will be even (candidates with odd n are sieved away by the prime 3), and so we are in this situation.
For the present search, k=25 and k=49 have this property.
When k is an odd square divisible by 3, it depends on whether n is even or odd. I think no example is known here where n is even. And we are not going to find any with k=9 because even n can be definitively ruled out in this case (see initial post by Ravi above).
/JeppeSN  

Ravi FernandoProject administrator Volunteer tester Project scientist Send message
Joined: 21 Mar 19 Posts: 205 ID: 1108183 Credit: 11,571,173 RAC: 4,503

Since we finished the last k=19683 task a few days ago, I thought I'd post the full list of primes here. The segment below n=300K (24 primes) was tested by me and doublechecked by JimB, and the rest (8 primes) was done on PrimeGrid.
19683*2^n + 1 is prime for n = 1, 5, 8, 32, 50, 400, 536, 592, 676, 866, 1157, 1300, 1661, 1730, 2440, 7046, 9698, 16180, 16226, 22330, 26990, 206005, 238780, 278941, 366665, 485845, 493846, 901745, 1797997, 1868828, 2033900, 2265896, and no other n < 4000000.  

Message boards :
Fermat Divisor Search :
What primes can be Fermat divisors? 