## Other

drummers-lowrise

Message boards : Proth Prime Search : Suggestion: a 5-7-9 Proth project

 Subscribe SortOldest firstNewest firstHighest rated posts first
Author Message
Message 131449 - Posted: 25 Jul 2019 | 16:22:52 UTC

I propose a new 5-7-9 Proth project to search exclusively for primes of the form:

5*2^n + 1
7*2^n + 1
9*2^n + 1

For the time being, we are not searching for Proth primes with these small k values. In the threads Where are PPS mega k=15 to 99? and Status and strategy for small k values, JimB has explained really well why it is so.

We want all candidates being sent out for one project at a particular day, to be comparable in size. Therefore, we are in the process making the larger k (still below 1200) "catch" up with the old leading edge for k=9, k=7, and k=5. As I said, JimB explained this well in the threads I linked, and also explained the history of Proth search here at PrimeGrid.

A new project to focus on 5-7-9 would be a good supplement to (the plus-form half of) the 321 project, in my opinion.

And the reason I favor these small k multipliers? Such primes are virtually certain to divide some extended generalized Fermat (xGF) numbers. And also has a higher chance of dividing GF or genuine Fermat (F) numbers.

And before anyone asks "Where's the proof 5-7-9 primes will divide ((x)G)F numbers more frequently, I have compiled a list here. See below. I can also appeal to the explanations given in the linked threads.

The following list contains all known 5-7-9 Proth primes with more than 100K decimal figures. No cherry picking. There are both primes found by PrimeGrid, primes found before the birth of PrimeGrid, and primes found by "lone" searchers searching "ahead" of PrimeGrid's search limit at the time. As you see, all of them are divisors.

k=5, all known primes with more than 100,000 digits: 5*2^819739+1 5*2^819739+1 divides GF(819738,3) 5*2^819739+1 divides xGF(819735,5,2) 5*2^819739+1 divides xGF(819738,6,5) 5*2^819739+1 divides xGF(819736,7,2) 5*2^819739+1 divides xGF(819736,7,5) 5*2^819739+1 divides xGF(819738,7,6) 5*2^819739+1 divides xGF(819737,11,8) 5*2^1282755+1 5*2^1282755+1 divides GF(1282754,3) 5*2^1282755+1 divides GF(1282748,5) 5*2^1282755+1 divides xGF(1282754,5,3) 5*2^1282755+1 divides xGF(1282754,7,4) 5*2^1282755+1 divides xGF(1282753,9,5) 5*2^1282755+1 divides xGF(1282754,11,8) 5*2^1282755+1 divides xGF(1282751,12,7) 5*2^1320487+1 5*2^1320487+1 divides xGF(1320486,5,3) 5*2^1320487+1 divides xGF(1320485,7,4) 5*2^1320487+1 divides xGF(1320486,8,3) 5*2^1320487+1 divides xGF(1320479,8,5) 5*2^1320487+1 divides xGF(1320485,9,2) 5*2^1320487+1 divides xGF(1320485,11,4) 5*2^1320487+1 divides xGF(1320484,11,7) 5*2^1320487+1 divides GF(1320486,12) 5*2^1777515+1 5*2^1777515+1 divides GF(1777511,5) 5*2^1777515+1 divides GF(1777514,6) 5*2^1777515+1 divides xGF(1777514,6,5) 5*2^1777515+1 divides GF(1777514,7) 5*2^1777515+1 divides xGF(1777514,7,5) 5*2^1777515+1 divides xGF(1777513,7,6) 5*2^1777515+1 divides xGF(1777513,9,8) 5*2^1777515+1 divides xGF(1777512,11,3) k=7, all known primes with more than 100,000 digits: 7*2^561816+1 7*2^561816+1 divides GF(561815,5) 7*2^561816+1 divides GF(561815,6) 7*2^561816+1 divides xGF(561810,6,5) 7*2^561816+1 divides xGF(561813,11,4) 7*2^804534+1 7*2^804534+1 divides xGF(804531,5,4) 7*2^804534+1 divides xGF(804532,9,8) 7*2^804534+1 divides xGF(804532,10,9) 7*2^804534+1 divides xGF(804531,11,2) 7*2^804534+1 divides GF(804533,12) 7*2^811230+1 7*2^811230+1 divides GF(811228,5) 7*2^811230+1 divides GF(811224,7) 7*2^811230+1 divides xGF(811228,7,5) 7*2^811230+1 divides xGF(811228,9,2) 7*2^811230+1 divides xGF(811226,10,9) 7*2^811230+1 divides xGF(811229,11,8) 7*2^1491852+1 7*2^1491852+1 divides GF(1491851,6) 7*2^1491852+1 divides xGF(1491848,7,4) 7*2^1491852+1 divides xGF(1491851,9,5) 7*2^1491852+1 divides xGF(1491842,10,3) 7*2^1491852+1 divides xGF(1491847,11,3) 7*2^1491852+1 divides xGF(1491847,11,10) 7*2^2139912+1 7*2^2139912+1 divides xGF(2139911,5,2) 7*2^2139912+1 divides xGF(2139908,7,4) 7*2^2139912+1 divides xGF(2139910,9,8) 7*2^2139912+1 divides xGF(2139911,10,7) 7*2^2139912+1 divides xGF(2139910,11,3) 7*2^2139912+1 divides GF(2139911,12) 7*2^2167800+1 7*2^2167800+1 divides F(2167797)! 7*2^2167800+1 divides GF(2167799,5) 7*2^2167800+1 divides xGF(2167799,5,2) 7*2^2167800+1 divides xGF(2167799,5,4) 7*2^2167800+1 divides GF(2167794,7) 7*2^2167800+1 divides xGF(2167797,7,2) 7*2^2167800+1 divides xGF(2167796,7,4) 7*2^2167800+1 divides xGF(2167799,7,5) 7*2^2167800+1 divides xGF(2167799,8,5) 7*2^2167800+1 divides xGF(2167797,8,7) 7*2^2167800+1 divides GF(2167799,10) 7*2^2167800+1 divides xGF(2167799,10,7) 7*2^2915954+1 7*2^2915954+1 divides xGF(2915951,5,2) 7*2^2915954+1 divides xGF(2915948,7,2) 7*2^2915954+1 divides xGF(2915951,7,5) 7*2^2915954+1 divides xGF(2915952,9,8) 7*2^2915954+1 divides GF(2915951,11) 7*2^2915954+1 divides GF(2915953,12) 7*2^2915954+1 divides xGF(2915953,12,11) 7*2^3015762+1 7*2^3015762+1 divides xGF(3015759,5,2) 7*2^3015762+1 divides xGF(3015761,8,3) 7*2^3015762+1 divides xGF(3015760,9,7) 7*2^3015762+1 divides xGF(3015759,12,11) 7*2^3511774+1 7*2^3511774+1 divides GF(3511773,6) 7*2^3511774+1 divides GF(3511770,7) 7*2^3511774+1 divides xGF(3511773,7,6) 7*2^3511774+1 divides xGF(3511771,10,9) 7*2^5775996+1 7*2^5775996+1 divides xGF(5775995,5,4) 7*2^5775996+1 divides xGF(5775995,7,6) 7*2^5775996+1 divides xGF(5775994,9,2) 7*2^5775996+1 divides xGF(5775993,11,4) 7*2^5775996+1 divides xGF(5775995,11,5) k=9, all known primes with more than 100,000 digits: 9*2^384990+1 9*2^384990+1 divides xGF(384989,5,3) 9*2^384990+1 divides xGF(384985,9,9) 9*2^384990+1 divides xGF(384989,12,7) 9*2^412034+1 9*2^412034+1 divides xGF(412030,4,3) 9*2^412034+1 divides xGF(412033,5,3) 9*2^412034+1 divides xGF(412033,5,4) 9*2^412034+1 divides xGF(412032,7,3) 9*2^412034+1 divides xGF(412032,7,2) 9*2^412034+1 divides xGF(412033,7,5) 9*2^412034+1 divides xGF(412033,11,3) 9*2^412034+1 divides xGF(412033,11,4) 9*2^412034+1 divides xGF(412032,11,5) 9*2^412034+1 divides xGF(412033,11,7) 9*2^435743+1 9*2^435743+1 divides xGF(435741,7,6) 9*2^435743+1 divides xGF(435734,9,2) 9*2^435743+1 divides GF(435742,10) 9*2^435743+1 divides xGF(435742,11,6) 9*2^435743+1 divides xGF(435742,11,7) 9*2^461081+1 9*2^461081+1 divides F(461076)! 9*2^461081+1 divides GF(461077,3) 9*2^461081+1 divides xGF(461077,3,2) 9*2^461081+1 divides xGF(461077,4,3) 9*2^461081+1 divides GF(461077,6) 9*2^461081+1 divides xGF(461077,8,3) 9*2^461081+1 divides xGF(461075,9,2) 9*2^461081+1 divides xGF(461074,9,8) 9*2^461081+1 divides GF(461080,11) 9*2^461081+1 divides xGF(461080,11,2) 9*2^461081+1 divides xGF(461080,11,3) 9*2^461081+1 divides xGF(461080,11,4) 9*2^461081+1 divides xGF(461080,11,6) 9*2^461081+1 divides xGF(461080,11,8) 9*2^461081+1 divides xGF(461080,11,9) 9*2^461081+1 divides GF(461077,12) 9*2^461081+1 divides xGF(461080,12,11) 9*2^834810+1 9*2^834810+1 divides xGF(834809,5,4) 9*2^834810+1 divides GF(834809,7) 9*2^834810+1 divides xGF(834806,9,8) 9*2^834810+1 divides xGF(834809,10,9) 9*2^834810+1 divides xGF(834809,11,6) 9*2^1051026+1 9*2^1051026+1 divides xGF(1051025,8,7) 9*2^1051026+1 divides xGF(1051025,9,7) 9*2^1051026+1 divides xGF(1051022,9,8) 9*2^1051026+1 divides xGF(1051025,10,3) 9*2^1051026+1 divides GF(1051024,11) 9*2^1807574+1 9*2^1807574+1 divides xGF(1807570,4,3) 9*2^1807574+1 divides xGF(1807572,7,6) 9*2^1807574+1 divides xGF(1807572,8,7) 9*2^2543551+1 9*2^2543551+1 divides F(2543548)! 9*2^2543551+1 divides GF(2543549,3) 9*2^2543551+1 divides xGF(2543549,3,2) 9*2^2543551+1 divides xGF(2543549,4,3) 9*2^2543551+1 divides GF(2543549,6) 9*2^2543551+1 divides xGF(2543549,8,3) 9*2^2543551+1 divides xGF(2543542,9,2) 9*2^2543551+1 divides xGF(2543547,9,8) 9*2^2543551+1 divides GF(2543550,11) 9*2^2543551+1 divides xGF(2543550,11,2) 9*2^2543551+1 divides xGF(2543550,11,3) 9*2^2543551+1 divides xGF(2543550,11,4) 9*2^2543551+1 divides xGF(2543550,11,6) 9*2^2543551+1 divides xGF(2543550,11,8) 9*2^2543551+1 divides xGF(2543550,11,9) 9*2^2543551+1 divides GF(2543549,12) 9*2^2543551+1 divides xGF(2543550,12,11) 9*2^3497442+1 9*2^3497442+1 divides GF(3497441,7) 9*2^3497442+1 divides xGF(3497438,9,8) 9*2^3497442+1 divides GF(3497441,10) 9*2^3497442+1 divides xGF(3497440,10,7) 9*2^3497442+1 divides xGF(3497439,11,3) 9*2^3497442+1 divides xGF(3497441,12,5) 9*2^5642513+1 (Serge Batalov in 2013, ahead of PrimeGrid's 2019 leading edge) 9*2^5642513+1 divides xGF(5642511,5,3) 9*2^5642513+1 divides GF(5642510,7) 9*2^5642513+1 divides xGF(5642509,9,2) 9*2^5642513+1 divides xGF(5642512,12,11)

Source: W. Keller: Factors of generalized Fermat numbers found after BjÃ¶rn & Riesel (I may have made some errors) and C. K. Caldwell: Prime Pages, Database Search Query (to make sure I did not miss any known prime over 100K digits)

/JeppeSN

Message 131450 - Posted: 25 Jul 2019 | 17:47:16 UTC - in response to Message 131449.

Looks like nice new badge (if we ever get it) :)
____________
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!

Message 131451 - Posted: 25 Jul 2019 | 17:49:00 UTC

I did the same search on k=3.

There's 12 primes with at least 100 thousand digits.

All of them are Generalized Fermat divisors (not Extended Generalized Fermat Divisors), and three (!!!) of them are Fermat divisors.

Obviously, the powers that be at the time agreed with you, since those k's were already searched to such high n values. There's obviously value in searching them.

But searching k=3 is even better.

The question isn't really "Should we search 5, 7, and 9?" The question is really "How do we want to divide the search amongst the low k's?"

You bring up an interesting proposition. That all of those primes are xGFN divisors is something I didn't know, nor did I know that all of the k=3 primes are GFN divisors.

One thing's for sure... we need to push 321 harder. The next Fermat divisor is going to be huge.

I'll think about 5, 7, and 9, and see what the others have to say about it. Thanks for the insight!
____________
My lucky number is 75898524288+1

Message 131453 - Posted: 25 Jul 2019 | 20:22:36 UTC - in response to Message 131451.

The question isn't really "Should we search 5, 7, and 9?" The question is really "How do we want to divide the search amongst the low k's?"

I agree! 5-7-9 is just a suggestion. Maybe 5-7 alone would be better, or maybe we should take 5-7-9-11-13-15 or something. My choice of 5-7-9 is kind of arbitrary. I just believe it would be very nice with an extremely-low-k Proth project. /JeppeSN

Message 131456 - Posted: 25 Jul 2019 | 20:57:21 UTC

For those of us who love OEIS, here are some sequence related to this discussion:

(X3) A002253 Numbers n such that 3*2^n+1 is prime.

(Y3) A204620 Numbers k such that 3*2^k + 1 is a prime factor of a Fermat number 2^(2^m) + 1 for some m.

(X5) A002254 Numbers k such that 5*2^k + 1 is prime.

(Y5) A226366 Numbers k such that 5*2^k + 1 is a prime factor of a Fermat number 2^(2^m) + 1 for some m.

(X7) A032353 Numbers n such that 7*2^n+1 is prime.

(Y7) A280003 Numbers n such that 7*2^n + 1 is a prime factor of a Fermat number 2^(2^m) + 1 for some m.

(X9) A002256 Numbers n such that 9*2^n+1 is prime.

(Y9) A280004 Numbers n such that 9*2^n + 1 is a prime factor of a Fermat number 2^(2^m) + 1 for some m.

Sorry for the inconsistent use of k and n in the titles. They are lists of what we call n here in the Proth search projects (but in OEIS, the letter n is often reserved for the index of each entry, so the letter n should probably not be used there, but as you see, it frequently is).

For (X3), both even and odd exponents occur. But Morehead noted in 1906 that the terms in (Y3) will always be odd! This means that when we find a 3*2^n+1 prime (in the 321 project), if n is even, there is no hope it will divide a true Fermat number. But it is still going to divide a bunch of GF and/or xGF numbers.

For (X5), only odd exponents occur (sieving with 3 removes all even n), and then the subsequence (Y5) is odd as well. For (X7) the entries are even (again, sieving with 3), and so (Y7) is even.

But then for (X9), both even and odd terms occur again. For (Y9), only four terms are known; is it a coincidence that all four (Y9) terms are odd? Does anyone know?

I know that (Y21) (not in OEIS, but equals 41, 276, 94801, â€¦) and (Y57) (not in OEIS, 25010, 146223, 2747499, â€¦) contain a mixture of even and odd.

If there is nothing theoretical preventing it, I would like to find an even member of (Y9).

/JeppeSN

Message 131457 - Posted: 25 Jul 2019 | 21:00:02 UTC

I did some more looking at existing primes. While I agree that a higher percentage of low-k primes will be divisors, that's not the whole story.

To date, PrimeGrid has found 19 Fermat divisors.

Number of Fermat Divisors with k=3: Zero
Number of Fermat Divisors with k=5: Zero
Number of Fermat Divisors with k=7: Zero
Number of Fermat Divisors with k=9: 1
Number of Fermat Divisors with 10<k<100: 3
Number of Fermat Divisors with 100<k<1200: 9
Number of Fermat Divisors with 1200<k<10000: 6

Despite 3, 5, 7, and 9 having been searched to a much higher n, we've found only a single Fermat divisor in those four k's combined. At the same time, we've found 18 Fermat divisors in larger k's, while searching at much smaller n's. If we want to find divisors, we've pretty much run the well dry on those low k's. The numbers are now too large and take too long to test. The higher k's are where we're going to find the divisors now. Quantity wins over quality in this case.
____________
My lucky number is 75898524288+1

Message 131459 - Posted: 25 Jul 2019 | 22:14:14 UTC

If the goal is to find as many Fermat divisors as possible, then we should find the right balance between looking at small k (more likely to be Fermat divisors if prime) and looking at small n (faster to test and more likely to be prime). The ratio of computational cost to probability of success is what Chris Caldwell calls the weight here. Lower weight means higher chance of yielding a Fermat divisor per unit time.

My proposal would be for a project called Fermat Divisor Search that searches all Proth candidates with small k in order of increasing weight. For example, to get up to ln(weight) = 50 we'd search:

k=3 to n=6.96M (321 is way past this already)
k=5 to n=5.89M (low-k PPS is slightly past this)
k=7 to n=5.28M (same)
k=9 to n=4.86M
k=11 to n=4.56M
k=13 to n=4.31M
k=15 to n=4.12M
k=17 to n=3.95M
k=19 to n=3.81M
k=21 to n=3.69M
k=23 to n=3.58M (PPS-MEGA is past this)
etc.

So we could start with something like k=9 through 21, adding in k's as we reach the appropriate thresholds.

Of course, I don't know how much of a pain it would be to administer a project like this, or what searching has been done outside of PrimeGrid. But I think something like this would give us a much better chance of finding Fermat divisors than the current PPS(E) search parameters. Let's compare some ln(weight)'s at current leading edges:

k=11, n ~ 3.64M: 49.31
k=9, n ~ 4M: 49.40
k=13, n ~ 3.64M: 49.48

k=1201, n ~ 1.543M (low PPSE): 51.37
k=301, n ~ 2.793M (low PPS): 51.80
k=1199, n ~ 2.793M (high PPS): 53.19
k=9999, n ~ 1.543M (high PPSE): 53.49

These numbers are on a log scale, so even a difference of 2-3 means an order-of-magnitude improvement in our chances of finding a Fermat divisor.

Message 131460 - Posted: 25 Jul 2019 | 22:16:05 UTC - in response to Message 131457.

I did some more looking at existing primes. While I agree that a higher percentage of low-k primes will be divisors, that's not the whole story.

To date, PrimeGrid has found 19 Fermat divisors.

Number of Fermat Divisors with k=3: Zero
Number of Fermat Divisors with k=5: Zero
Number of Fermat Divisors with k=7: Zero
Number of Fermat Divisors with k=9: 1
Number of Fermat Divisors with 10<k<100: 3
Number of Fermat Divisors with 100<k<1200: 9
Number of Fermat Divisors with 1200<k<10000: 6

Despite 3, 5, 7, and 9 having been searched to a much higher n, we've found only a single Fermat divisor in those four k's combined. At the same time, we've found 18 Fermat divisors in larger k's, while searching at much smaller n's. If we want to find divisors, we've pretty much run the well dry on those low k's. The numbers are now too large and take too long to test. The higher k's are where we're going to find the divisors now. Quantity wins over quality in this case.

Part of the reason is that other people are finding the 5-7-9 primes. Your table covers 19 primes.

For k=7, there is a Fermat divisor 7*2^2167800 + 1 which is greater than 15 of those 19 primes. It was found by Curtis Cooper in 2007.

For k=9, there is a Fermat divisor 9*2^461081 + 1 which is greater than 4 of your 19 primes. It was found by Takahiro Nohara in 2003.

So Fermat divisors with 7 and 9 exist in this "range", but the reason they are not counted in your statistics is that people outside PrimeGrid prioritized them before PrimeGrid got to search there.

The fact that other people have focused on small k, should not mean that it is a bad strategy for us to focus on small k.

When we look at all 5-7-9 Proth primes (divisors or not), we have the following:

k=5:
n = 1, 3, 7, 13, 15, 25, 39, 55, 75, 85, 127, 1947, 3313, 4687, 5947, 13165, 23473, 26607, 125413, 209787, 240937, 819739, 1282755, 1320487, 1777515.

k=7:
n = 2, 4, 6, 14, 20, 26, 50, 52, 92, 120, 174, 180, 190, 290, 320, 390, 432, 616, 830, 1804, 2256, 6614, 13496, 15494, 16696, 22386, 54486, 88066, 95330, 207084, 283034, 561816, 804534, 811230, 1491852, 2139912, 2167800, 2915954, 3015762, 3511774, 5775996.

k=9:
n = 1, 2, 3, 6, 7, 11, 14, 17, 33, 42, 43, 63, 65, 67, 81, 134, 162, 206, 211, 366, 663, 782, 1305, 1411, 1494, 2297, 2826, 3230, 3354, 3417, 3690, 4842, 5802, 6937, 7967, 9431, 13903, 22603, 24422, 39186, 43963, 47003, 49902, 67943, 114854, 127003, 145247, 147073, 149143, 304607, 384990, 412034, 435743, 461081, 834810, 1051026, 1807574, 2543551, 3497442, 5642513.

The numbers in bold are the ones found by PrimeGrid. To me it looks like PrimeGrid has sometimes missed some primes here. Could that be an indication that PrimeGrid does not prioritize these small k candidate as highly as we should?

For big values of k, I think PrimeGrid has found each and every prime. So that skews the statistics somewhat.

/JeppeSN

Message 131461 - Posted: 25 Jul 2019 | 22:35:09 UTC - in response to Message 131459.

If the goal is to find as many Fermat divisors as possible, then we should find the right balance between looking at small k (more likely to be Fermat divisors if prime) and looking at small n (faster to test and more likely to be prime). The ratio of computational cost to probability of success is what Chris Caldwell calls the weight here. Lower weight means higher chance of yielding a Fermat divisor per unit time.

My proposal would be for a project called Fermat Divisor Search that searches all Proth candidates with small k in order of increasing weight. For example, to get up to ln(weight) = 50 we'd search:

k=3 to n=6.96M (321 is way past this already)
k=5 to n=5.89M (low-k PPS is slightly past this)
k=7 to n=5.28M (same)
k=9 to n=4.86M
k=11 to n=4.56M
k=13 to n=4.31M
k=15 to n=4.12M
k=17 to n=3.95M
k=19 to n=3.81M
k=21 to n=3.69M
k=23 to n=3.58M (PPS-MEGA is past this)
etc.

So we could start with something like k=9 through 21, adding in k's as we reach the appropriate thresholds.

Of course, I don't know how much of a pain it would be to administer a project like this, or what searching has been done outside of PrimeGrid. But I think something like this would give us a much better chance of finding Fermat divisors than the current PPS(E) search parameters.

Excellent post! Of course this is the way it "ought" to be. But I think it is hard to administer. And if we followed such a "curved" leading edge, it would be frustrating to many users that you could not know in advance if you got a {k=3, n=6.96M} candidate (takes a long time to test) or a {k=23, n=3.58M} candidate (much shorter testing time).

Let's compare some ln(weight)'s at current leading edges:

k=11, n ~ 3.64M: 49.31
k=9, n ~ 4M: 49.40
k=13, n ~ 3.64M: 49.48

k=1201, n ~ 1.543M (low PPSE): 51.37
k=301, n ~ 2.793M (low PPS): 51.80
k=1199, n ~ 2.793M (high PPS): 53.19
k=9999, n ~ 1.543M (high PPSE): 53.49

These numbers are on a log scale, so even a difference of 2-3 means an order-of-magnitude improvement in our chances of finding a Fermat divisor.

Exactly. And this is going to be much much worse if PrimeGrid realizes their current plan which is to stop work on all small k until every k from 5 through 1199 is at the same n.

:-(

/JeppeSN

Message 131462 - Posted: 26 Jul 2019 | 1:41:50 UTC

A few remarks on GF and xGF divisors:

A prime p is a Fermat divisor if and only if the multiplicative order of 2 modulo p is a power of 2. This generalizes to GF's and xGF's: p divides a GF(something, b) if and only if the multiplicative order of b modulo p is a power of 2, and it divides an xGF(something, a, b) if and only if the multiplicative order of a/b is a power of 2. (The division here is mod-p division, and I am excluding the degenerate cases where p divides a, b, or a-b.)

So let's talk about heuristics. If p = k*2^n+1 with k odd, then there are p-1 = k*2^n units modulo p, and exactly 2^n of them have multiplicative orders equal to a power of 2. So a reasonable baseline guess is that the multiplicative order of a typical number (2, 3, 8/7, etc.) is a power of 2 with probability 1/k, and therefore that p has a 1/k chance of dividing an xGF with any given parameters a, b.

Aside: these events aren't independent; in particular, the "multiplicative order" criterion implies that if p divides an xGF for some (a, b) and also for (a, c), then it divides one for (b, c) as well. But let's say we're only interested in how many ((x)G)F divisors we find, and we don't care about whether they're the same prime or different ones. Then linearity of expectations says that the expected number of xGF divisors found is the sum of the individual probabilities.

Second aside: the probability of dividing a GF(something, 8) is actually 3 times better when k is divisible by 3, because 8 is already a cube. In particular, a prime of the form 3*2^n+1 always divides a GF(something, 8). (Except for the degenerate case 3*2+1 = 7.) This explains Michael Goetz's observation.

My understanding is that we track Fermat divisors, GF divisors for 8 values of b (3, 5, 6, 7, 8, 10, 11, 12), and xGF divisors for each of the 33 relatively prime pairs (a, b) with 1 < b < a <= 12, excluding (9, 4) because it's equivalent to (3, 2). So a prime p = k*2^n+1 should on average divide 42/k xGF numbers, including 9/k GF numbers, including 1/k Fermat numbers.

All of this is basically to say that some constant multiple of the probability of finding a Fermat prime is a good proxy for the expected number of (x)GF's we find. Except for errors in the 1/k heuristic (e.g. the second aside above, Morehead's theorem on 321 numbers, and probably others I'm not aware of), the constant involved in this statement shouldn't depend on k. So optimizing for Fermat divisors should be roughly the same as optimizing for (x)GF divisors.

Message 131463 - Posted: 26 Jul 2019 | 2:27:46 UTC - in response to Message 131461.

Excellent post! Of course this is the way it "ought" to be. But I think it is hard to administer. And if we followed such a "curved" leading edge, it would be frustrating to many users that you could not know in advance if you got a {k=3, n=6.96M} candidate (takes a long time to test) or a {k=23, n=3.58M} candidate (much shorter testing time).

Good point. In the short term, testing something like k=9..21 uniformly would be a pretty good approximation of the "optimal" strategy for looking for large Fermat divisors, but it's hard to see how to manage the search in the longer term without either testing different sizes in parallel or switching ranges frequently. And of course at some point this project would take us out of our current sieve files.

Exactly. And this is going to be much much worse if PrimeGrid realizes their current plan which is to stop work on all small k until every k from 5 through 1199 is at the same n.

It's a question of priorities. If your main goal is to find Fermat divisors, you search small k's deeper. If your main goal is to find lots of T5K primes, or to minimize administrative headaches, you search uniformly. We leaned more toward the former in the old days and toward the latter now, and this is probably one of the reasons (although certainly not the only one) why we haven't found any Fermat divisors since 2015. But if the admins see fit to add something focusing on low-double-digit k's, I'm sure there would be interest in it.

Message 131465 - Posted: 26 Jul 2019 | 8:28:43 UTC

Ravi Fernando, thanks for your insightful explanations.

Back in February, in the thread Where are PPS mega k=15 to 99?, people (including myself) also tried to promote the 1/k philosophy.

From your example with Fermat divisor "weight" of Proth primes, I realize that the k interval from 11 to 21, for example, which is not included in my 5-7-9 proposal, is currently where the "cheap" ((x)G)F divisors may lurk.

Still to keep things simple, administratively, I think it would be best to pick a k interval starting from 5. But 5-7-9-11-13-15-17-19-21 is also a possibility. Of course if we did that, after a while the "cheap" divisors would be in 23-25-etc.

Frequent changes in k and n search domains is one way to better approximate the theoretical "weight"-optimized, curved leading edge, but I think JimB and others have said quite clearly that they do not want to manage such a scenario.

/JeppeSN

Yves Gallot
Volunteer developer
Project scientist

Joined: 19 Aug 12
Posts: 644
ID: 164101
Credit: 305,010,093
RAC: 0 Message 131468 - Posted: 26 Jul 2019 | 10:29:15 UTC

[Sorry, I missed some messages when I posted this one... it means that I agree with Ravi Fernando but with a different definition of the "weight"]

I think that the suggestion is to search for the largest known Fermat factor.
Today PPS Mega is the best placed to succeed (this search found the largest known Fermat factor 193â€ŠÂ·â€Š23329782+1).
321 is not efficient because neither 3â€ŠÂ·2n-1 nor 3â€ŠÂ·22n+1 can divide a Fermat number.

We know that
Prob(kâ€ŠÂ·2n+1 is prime) ~ 1 / log(kâ€ŠÂ·2n+1) ~ C / n
and if P=kâ€ŠÂ·2n+1 is prime then Prob(P divides a Fermat number) ~ 1 / k
Then we have
Prob(kâ€ŠÂ·2n+1 divides a Fermat number) ~ C / (kâ€ŠÂ·n)
[That's the log(k)â€ŠÂ·log(n) distribution: http://www.fermatsearch.org/math.html]

For the largest known Fermat factor search, a good idea might be to send candidates such that kâ€ŠÂ·n is constant:
321 is testing n ~ 15,000,000
3Â·â€Š215000000+1 <=> kÂ·â€Š215000000Â·3/kâ€Š+1
k = 5 => n = 9,000,000
k = 7 => n = 6,428,571
k = 9 => n = 5,000,000
k = 11 => n = 4,090,909
k = 13 => n = 3,461,538
according to http://www.primegrid.com/stats_pps_llr.php we already have nmax = 3,322,000 for k < 100 ???

Message 131478 - Posted: 26 Jul 2019 | 13:17:04 UTC - in response to Message 131468.

For the largest known Fermat factor search, a good idea might be to send candidates such that kâ€ŠÂ·n is constant:

OK, so we have two ideas on how an ideal "curved leading edge" (I call it curved because I think of a linear (k,n) diagram) might look. Yves Gallot and Luigi Morelli/Leonid Durman form is

k*n = constant

And Ravi Fernando and Chris Caldwell form is approximately equivalent to

k*n^3 = constant

But wait, what is the slope of that diagonal in fermatsearch.org's diagram?

Maybe we can agree on k*n^a = constant for some relevant fixed a?

/JeppeSN

Addition: Attempting some high-school math on the equation k*n^a = constant where two points (n1, k1) = (7, 7e14) and (n2, k2) = (5e5, 3) are given, I solve for the exponent a to get

a = 2.96

It is log(7e14 / 3) / log(5e5 / 7), to be precise.

Even later addition: Not until now do I notice the formula for the diagonal given in the diagram, k = e^(40 - 3 ln n). It is equivalent to k = e^40 * n^(-3). In other words:

k*n^3 = e^40

You can see how the "diagonal" does not actually meet the vertex of the red rectangle in the lower right corner. That's why a=2.96 when looking at the rectangle, and a=3 exactly when looking at the diagonal.

Message 131488 - Posted: 26 Jul 2019 | 17:46:34 UTC - in response to Message 131468.

I think that the suggestion is to search for the largest known Fermat factor.
Today PPS Mega is the best placed to succeed (this search found the largest known Fermat factor 193â€ŠÂ·â€Š23329782+1).

That was true until earlier this month, when MEGA was switched to the PPSE range 1200<k<10000. These candidates are smaller than the record, and are also less likely to be Fermat divisors. In fact, the current candidates have ln(weight) between 53.72 (k=1201) and 55.84 (k=9999). The current 321 candidates (n ~ 14.94M) have ln(weight) ~ 52.34. Adding ln(5)~1.61 to account for the fact that ~80% of 321 candidates can't be Fermat divisors, this is still more efficient than most current MEGA candidates.

For the largest known Fermat factor search, a good idea might be to send candidates such that kâ€ŠÂ·n is constant

This will maximize the probability of finding a record Fermat divisor per primality test, but not per unit time. If a leading-edge 321 test is just as likely to produce a Fermat divisor as an n~4M test for k=11, the latter is a better use of time--unless of course you consider big Fermat divisors to be proportionally more valuable. (Which is fair enough I guess.)

Message 131489 - Posted: 26 Jul 2019 | 18:39:59 UTC

For what it's worth, none of PrimeGrid's projects are intended to be Fermat divisor searches. It's just an added bonus. I'm not saying we couldn't run such a search in the future, but the design of our current projects do not prioritize finding divisors.

I'm mentioning this only because you shouldn't think of the current projects in the context of "it was set thusly to have such and such a chance to find divisors." Each project has its own goals, and explicitly finding divisors isn't one of them.

GFN aside, each project either has a special purpose (SGS, factorial, primorial), is a conjecture, or otherwise is just an easy way to find reportable primes or an easy way to find mega primes.

____________
My lucky number is 75898524288+1

Message 131491 - Posted: 26 Jul 2019 | 20:22:08 UTC - in response to Message 131488.

--unless of course you consider big Fermat divisors to be proportionally more valuable. (Which is fair enough I guess.)

To me, any Fermat factor is interesting. Big or small.

Obviously, some small ones which are extremely "wanted", like more factors of F12, F13, F14 (the smallest ones for which we do not know all factors yet), or factors of F20 or F24 (for which a primality test shows that factors exist, but none are known), or factors of F33, F34, F35 (the first Fermat numbers for which we do not know if they are Fermat primes), can never be found by PrimeGrid's methods.

(At one point, PrimeGrid found a smallish factor which was not in itself big enough to make it into Top 5000, but did make it to the Top 20 for Fermat divisors and is therefore included in Caldwell's database. I do not think that will ever happen again.)

But a huge factor like 193*2^3329782 + 1 which proves that the ridiculously enormous Fermat number F3329780 = 2^(2^3329780) + 1 is composite, is also nice.

2^(2^3329780) + 1 is so colossally enormous that the smallest factor it can possibly have (of form k*2^(m+2) + 1) is necessarily a megaprime.

Well, I am being offtopic in my own thread now.

/JeppeSN

Yves Gallot
Volunteer developer
Project scientist

Joined: 19 Aug 12
Posts: 644
ID: 164101
Credit: 305,010,093
RAC: 0 Message 131499 - Posted: 27 Jul 2019 | 11:26:54 UTC - in response to Message 131488.

This will maximize the probability of finding a record Fermat divisor per primality test, but not per unit time. If a leading-edge 321 test is just as likely to produce a Fermat divisor as an n~4M test for k=11, the latter is a better use of time--unless of course you consider big Fermat divisors to be proportionally more valuable. (Which is fair enough I guess.)

I agree that kâ€ŠÂ·n3 is better if we search for all Fermat divisors.
But the big Fermat divisors are more valuable, not only because they are big but also because k is small.

The GFN are studied because we can find and check their properties and expect that some of them are true with Fermat numbers. The size of the Fermat numbers grows so quickly that it's very difficult to study them directly.
We can prove that the proportion btot of bases b < P = kâ€ŠÂ·2n+1 which have a GFN divisible by P is
btot / P = (1 - 1/2n) / (k + 1/2n) ~ 1 / k for large n.
[Factors of generalized Fermat numbers, Harvey Dubner and Wilfrid Keller, Math. Comp. 64 (1995), 397-405]

But as you noticed the question is what is the proportion for fixed b and especially for b = 2.

49 primes of the form 3â€ŠÂ·2n+1 are known. For 21 of them n is odd. They divide 8 Fermat numbers. 49 / 2 / 3 ~ 8 then the results are in accordance with the 1/3 ratio and Morehead's theorem.
25 primes of the form 5â€ŠÂ·2n+1 are known and 9 of them divide a Fermat number. This is clearly more than expected. Wilfrid Keller noticed this deviation and suggested that the search for 3 and 5 should be extended to the same limit.
k = 7, 9, 11, 13 have the expected ratio but for
k = 15: we have 60 primes and a single Fermat factor,
k = 17: 19 primes and 3 Fermat factors,
k = 19: 20 primes and 3 Fermat factors.
... just the disturbance of the statistical deviation or some anomalies?
If we want to detect it, the number of primes must be larger than k and then k be small.

For k = 5 there may be a sort of anti Morehead's theorem such that the ratio is larger than 1/5. Of course the knowledge of the primes of the form 5â€ŠÂ·2n+1 may facilitate to find it.

Following the advice of Wilfrid Keller, I would say that 3 is the most efficient and 5 the most interesting.

Message 132040 - Posted: 13 Aug 2019 | 18:40:22 UTC - in response to Message 131499.

Interesting idea, such an low-k Proth project.

I have done a small visualization of what has been done so far in the current Proth pojects and added the k n = const and k n^3 = const curves, normalized at the status of the 321 project.

After PPS reached the starting point of MEGA, maybe it can be utilized as a "low-k PPS" in order to close the gap below the k n^3 = const curve? Best regards,
A.

Message 132042 - Posted: 13 Aug 2019 | 20:24:07 UTC - in response to Message 132040.

Nice plot of the different PrimeGrid projects (including 27 and 121 from PRPNet). The "new" MEGA project is to the right of the MEGA box shown (therefore even further out on the "wrong" side of the dashed lines). The white areas to the left of (one or both) the dashed lines is where it might be best to search if your only interest was finding Fermat divisors. /JeppeSN

Message boards : Proth Prime Search : Suggestion: a 5-7-9 Proth project