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 : Fermat Divisor Search : What primes can be Fermat divisors?

Author Message
Ravi Fernando
Project administrator
Project scientist
Send message
Joined: 21 Mar 19
Posts: 53
ID: 1108183
Credit: 4,873,603
RAC: 7,236
321 LLR Silver: Earned 100,000 credits (224,754)ESP LLR Bronze: Earned 10,000 credits (16,570)PPS LLR Amethyst: Earned 1,000,000 credits (1,222,060)PSP LLR Bronze: Earned 10,000 credits (26,371)SoB LLR Silver: Earned 100,000 credits (183,524)SR5 LLR Bronze: Earned 10,000 credits (11,183)SGS LLR Silver: Earned 100,000 credits (101,660)TRP LLR Bronze: Earned 10,000 credits (72,462)321 Sieve Ruby: Earned 2,000,000 credits (2,940,256)AP 26/27 Bronze: Earned 10,000 credits (72,774)
Message 132659 - Posted: 7 Sep 2019 | 21:17:00 UTC

Some people have been asking why PPS-DIV 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 m-th 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 (1-6), 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 divisors--27 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 double-check the relevant work that's been done on PRPNet.

Profile JeppeSNProject donor
Avatar
Send message
Joined: 5 Apr 14
Posts: 1011
ID: 306875
Credit: 12,036,182
RAC: 14,547
Found 1 prime in the 2020 Tour de Primes321 LLR Silver: Earned 100,000 credits (360,928)Cullen LLR Bronze: Earned 10,000 credits (98,851)ESP LLR Silver: Earned 100,000 credits (139,922)Generalized Cullen/Woodall LLR Bronze: Earned 10,000 credits (35,236)PPS LLR Ruby: Earned 2,000,000 credits (2,932,550)PSP LLR Silver: Earned 100,000 credits (212,242)SoB LLR Silver: Earned 100,000 credits (237,390)SR5 LLR Bronze: Earned 10,000 credits (16,010)SGS LLR Bronze: Earned 10,000 credits (32,969)TRP LLR Bronze: Earned 10,000 credits (71,060)Woodall LLR Silver: Earned 100,000 credits (109,455)321 Sieve Silver: Earned 100,000 credits (175,037)PSA Turquoise: Earned 5,000,000 credits (7,614,290)
Message 132663 - Posted: 7 Sep 2019 | 22:16:14 UTC

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 Fernando
Project administrator
Project scientist
Send message
Joined: 21 Mar 19
Posts: 53
ID: 1108183
Credit: 4,873,603
RAC: 7,236
321 LLR Silver: Earned 100,000 credits (224,754)ESP LLR Bronze: Earned 10,000 credits (16,570)PPS LLR Amethyst: Earned 1,000,000 credits (1,222,060)PSP LLR Bronze: Earned 10,000 credits (26,371)SoB LLR Silver: Earned 100,000 credits (183,524)SR5 LLR Bronze: Earned 10,000 credits (11,183)SGS LLR Silver: Earned 100,000 credits (101,660)TRP LLR Bronze: Earned 10,000 credits (72,462)321 Sieve Ruby: Earned 2,000,000 credits (2,940,256)AP 26/27 Bronze: Earned 10,000 credits (72,774)
Message 132666 - Posted: 8 Sep 2019 | 0:08:47 UTC - in response to Message 132663.

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.

Profile JeppeSNProject donor
Avatar
Send message
Joined: 5 Apr 14
Posts: 1011
ID: 306875
Credit: 12,036,182
RAC: 14,547
Found 1 prime in the 2020 Tour de Primes321 LLR Silver: Earned 100,000 credits (360,928)Cullen LLR Bronze: Earned 10,000 credits (98,851)ESP LLR Silver: Earned 100,000 credits (139,922)Generalized Cullen/Woodall LLR Bronze: Earned 10,000 credits (35,236)PPS LLR Ruby: Earned 2,000,000 credits (2,932,550)PSP LLR Silver: Earned 100,000 credits (212,242)SoB LLR Silver: Earned 100,000 credits (237,390)SR5 LLR Bronze: Earned 10,000 credits (16,010)SGS LLR Bronze: Earned 10,000 credits (32,969)TRP LLR Bronze: Earned 10,000 credits (71,060)Woodall LLR Silver: Earned 100,000 credits (109,455)321 Sieve Silver: Earned 100,000 credits (175,037)PSA Turquoise: Earned 5,000,000 credits (7,614,290)
Message 132670 - Posted: 8 Sep 2019 | 0:54:03 UTC - in response to Message 132666.

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

Profile JeppeSNProject donor
Avatar
Send message
Joined: 5 Apr 14
Posts: 1011
ID: 306875
Credit: 12,036,182
RAC: 14,547
Found 1 prime in the 2020 Tour de Primes321 LLR Silver: Earned 100,000 credits (360,928)Cullen LLR Bronze: Earned 10,000 credits (98,851)ESP LLR Silver: Earned 100,000 credits (139,922)Generalized Cullen/Woodall LLR Bronze: Earned 10,000 credits (35,236)PPS LLR Ruby: Earned 2,000,000 credits (2,932,550)PSP LLR Silver: Earned 100,000 credits (212,242)SoB LLR Silver: Earned 100,000 credits (237,390)SR5 LLR Bronze: Earned 10,000 credits (16,010)SGS LLR Bronze: Earned 10,000 credits (32,969)TRP LLR Bronze: Earned 10,000 credits (71,060)Woodall LLR Silver: Earned 100,000 credits (109,455)321 Sieve Silver: Earned 100,000 credits (175,037)PSA Turquoise: Earned 5,000,000 credits (7,614,290)
Message 132689 - Posted: 8 Sep 2019 | 12:01:20 UTC
Last modified: 8 Sep 2019 | 12:04:23 UTC

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^{m-1}), a generalized Fermat prime is just a prime of form x^2 + 1, or "a near-square prime".

The fourth of Landau's problems (1912) asks if there are infinitely many primes of that type.

A near-square 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 Fernando
Project administrator
Project scientist
Send message
Joined: 21 Mar 19
Posts: 53
ID: 1108183
Credit: 4,873,603
RAC: 7,236
321 LLR Silver: Earned 100,000 credits (224,754)ESP LLR Bronze: Earned 10,000 credits (16,570)PPS LLR Amethyst: Earned 1,000,000 credits (1,222,060)PSP LLR Bronze: Earned 10,000 credits (26,371)SoB LLR Silver: Earned 100,000 credits (183,524)SR5 LLR Bronze: Earned 10,000 credits (11,183)SGS LLR Silver: Earned 100,000 credits (101,660)TRP LLR Bronze: Earned 10,000 credits (72,462)321 Sieve Ruby: Earned 2,000,000 credits (2,940,256)AP 26/27 Bronze: Earned 10,000 credits (72,774)
Message 133779 - Posted: 12 Oct 2019 | 1:18:41 UTC

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 double-checked 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.

Post to thread

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

[Return to PrimeGrid main page]
DNS Powered by DNSEXIT.COM
Copyright © 2005 - 2020 Rytis Slatkevičius (contact) and PrimeGrid community. Server load 1.53, 1.67, 1.95
Generated 25 Feb 2020 | 12:42:34 UTC