## Other

drummers-lowrise

Message boards : Proth Prime Search : Where are PPS mega k=15 to 99?

 Subscribe SortOldest firstNewest firstHighest rated posts first
Author Message
Message 126422 - Posted: 7 Feb 2019 | 7:52:39 UTC

Hey.

I'm adamantly waiting for PPS mega search to reach n=3.6M, since after that it will evidently start testing smaller k's that also have smaller FFT sizes.

However, on the stats page http://www.primegrid.com/stats_mega_llr.php, k's between 15 and 99 are missing. They are visible on PPS for up to n=3321992 (the mega limit). I can also find primes like 33*2^3570132+1 using the Primes by Project page.

Will those k's also start being tested at n=3.6M? What is the cause that we can only see k=11 and k=13 on the stats page?

Message 126423 - Posted: 7 Feb 2019 | 9:08:55 UTC - in response to Message 126422.

PPS Mega started on PRPNet, that's where those low-k candidates were tested. We never felt any great need to DC them. PPS Mega was then n=3.322M-3.6M.

k=3 is tested in 321
k=5 and k=7 were tested to n=6M years ago (I have no idea why)
k=9 was tested to n=4M years ago.
k=11-99 will start again at n=3.6M

The next PPS Mega candidate file to be loaded starts at n=3.6M so we'll soon have data on the stats page for those k's. I'm sure we'll be loading that during TdP.

Message 126425 - Posted: 7 Feb 2019 | 9:45:29 UTC - in response to Message 126423.

Next MEGAs are with larger n's? Why not with larger k's?

Message 126426 - Posted: 7 Feb 2019 | 10:16:10 UTC - in response to Message 126425.

Next MEGAs are with larger n's? Why not with larger k's?

If PPS mega would go up to higher k's, it would probably be to PPSE territory (k=1201 to 9999) for consistency.

A quick test shows that FFT sizes (that determine the efficiency of the test) for current k's 11 to 1199 for n=3.6M are much smaller or the same than for the higher k's at the mega limit.

Starting Proth prime test of 11*2^3600003+1
Using all-complex FMA3 FFT length 200K, Pass1=640, Pass2=320, 4 threads, a = 3

Starting Proth prime test of 101*2^3600003+1
Using all-complex FMA3 FFT length 256K, Pass1=128, Pass2=2K, 4 threads, a = 3

Starting Proth prime test of 501*2^3600003+1
Using all-complex FMA3 FFT length 256K, Pass1=128, Pass2=2K, 4 threads, a = 7

Starting Proth prime test of 1199*2^3600003+1
Using all-complex FMA3 FFT length 256K, Pass1=128, Pass2=2K, 4 threads, a = 3

And then for the higher k's (n drops from 3.6M to ~3.32M):

Starting Proth prime test of 3999*2^3321917+1
Using all-complex FMA3 FFT length 256K, Pass1=128, Pass2=2K, 4 threads, a = 11

Starting Proth prime test of 6999*2^3321918+1
Using all-complex FMA3 FFT length 256K, Pass1=128, Pass2=2K, 4 threads, a = 5

Starting Proth prime test of 9999*2^3321915+1
Using all-complex FMA3 FFT length 256K, Pass1=128, Pass2=2K, 4 threads, a = 5

So IMO it might not be the best idea to move to higher k's yet. Sure, there is less iterations to do, but the smaller k's are more efficient. And I like the fact that the leading edge goes up faster :)

Message 126445 - Posted: 7 Feb 2019 | 14:25:12 UTC

Fun fact:

The smaller 200K FFT size is actually slower than the 256K FFT size on my 7700K when using 4 threads. Using fewer threads is however faster.

Message 126446 - Posted: 7 Feb 2019 | 14:32:03 UTC - in response to Message 126445.

Fun fact:

The smaller 200K FFT size is actually slower than the 256K FFT size on my 7700K when using 4 threads. Using fewer threads is however faster.

It will be slower on 4 cores. But on 2 cores will be faster. Way faster
____________
92*10^1439761-1 NEAR-REPDIGIT PRIME :) :) :)
4 * 650^498101-1 CRUS PRIME
2022202116^131072+1 GENERALIZED FERMAT
Proud member of team Aggie The Pew. Go Aggie!

Message 126452 - Posted: 7 Feb 2019 | 15:00:42 UTC - in response to Message 126426.

When I took over loading PPS/PPSE/MEGA work, highest n values for different k's were all over the place. There didn't seem to be any reason for what was done. I'm bringing order to this, but it's taken years for other k values to catch up. Once they're all caught up, that's how they're going to stay.

The initial load of MEGA work on PRPNet was for k=9-99 with n values from 3.22M-3.6M. When that was finished we moved to the next 100 k's 101-299, then 301-399, then 401-499. We also tested k=11 from 3454226-3.6M and k=13 from 3513537-3.6M because they hadn't been fully loaded on PRPNet. Every time we moved to a new k range (and back to a lower n range), the candidates got smaller again. At that point we started loading k=501-1199 (the remaining PPS k range) in smaller n increments to bring the entire PPS k range up to n=3.6M. We're now arriving at that point and can start testing k=11-1199 with each candidate file having 20K n spans: 3.60M-3.62M, 3.62M-3.64M, etc. At n=4M, k=9 will be added back in. At n=6M, k=5,7 will be added back in. Candidate size will always be increasing.

We will not be going back to the piecemeal approach that prevailed prior to 2013. There were overlaps where candidates were tested more than once and missed ranges that were never tested (but have been now). I had to track all those ranges down and make sure everything had been tested.

At some point PPS will catch up to where MEGA starts, n=3.322M. That's years in the future and we haven't decided what we'll do then. It's possible that MEGA will go away or it could continue with k values 1201-9999 from the PPSE k range. On June 28, 2017 I created PPS candidate files for n values 2.6M-3.0M. We're currently running n=2.7M-2.725M. Running out of PPS candidates is at least five years away. Whoever is running PrimeGrid at that time will decide what to do about it.

P.S. Before anyone asks yet again, we only test odd k values. Why? Because that way we don't duplicate work. Let's pick a candidate with an even k and show why: 18*2n+1 is the same number as 9*2n+1+1. That holds true for all candidates where b=2.

rogue
Volunteer developer Joined: 8 Sep 07
Posts: 1255
ID: 12001
Credit: 18,565,548
RAC: 0  Message 126482 - Posted: 7 Feb 2019 | 20:58:17 UTC

Some of this history is also tied to the old prothsearch.net website. I maintained the Proth search reservations and updates for Ray Ballinger for years until he passed. Interest was waning in that search so PrimeGrid took it over. Jim and I worked together so that PrimeGrid would avoid poaching work done by the few remaining searchers using prothsearch. But after Ray passed, I saw no reason to continue the manual work at prothsearch.net. Now PrimeGrid has sole ownership over this search, which has been a huge boon to search.

Message 126509 - Posted: 8 Feb 2019 | 9:08:38 UTC

Here's some benchmarks on FFT size = 200K on the i7-7700K (k=11, n=3600003):

4 tasks, -t1, 0.69 ms per bit /4 = 0.1725 ms per bit "overall"
2 tasks, -t2, 0.48 ms per bit /2 = 0.24 ms per bit "overall"
1 task, -t4, 0.28 ms per bit

For comparison, with FFT = 256K, k=1199, n=3600003

4 tasks, -t1, 0.85 ms per bit / 4 = 0.2125 ms per bit "overall"
2 tasks, -t2, 0.43 ms per bit = 0.215 ms per bit "overall"
1 task, -t4, 0.233 ms per bit

Interestingly, the lower FFT size is much slower with multithreading, which really feels counter-intuitive. So keep this in mind when selecting multithreading for your machine. I'm definately going with -t1 on the i7-7700K.

Message 126562 - Posted: 9 Feb 2019 | 10:23:12 UTC - in response to Message 126423.

PPS Mega started on PRPNet, that's where those low-k candidates were tested. We never felt any great need to DC them. PPS Mega was then n=3.322M-3.6M.

k=3 is tested in 321
k=5 and k=7 were tested to n=6M years ago (I have no idea why)
k=9 was tested to n=4M years ago.
k=11-99 will start again at n=3.6M

The next PPS Mega candidate file to be loaded starts at n=3.6M so we'll soon have data on the stats page for those k's. I'm sure we'll be loading that during TdP.

Thanks for the info! I also talked about k=15-99 in my thread Status and strategy for small k values, and now these k appear on the Stats Mega LLR page! Will they start from n=3.32M? /JeppeSN

Message 126563 - Posted: 9 Feb 2019 | 10:31:04 UTC - in response to Message 126562.

PPS Mega started on PRPNet, that's where those low-k candidates were tested. We never felt any great need to DC them. PPS Mega was then n=3.322M-3.6M.

k=3 is tested in 321
k=5 and k=7 were tested to n=6M years ago (I have no idea why)
k=9 was tested to n=4M years ago.
k=11-99 will start again at n=3.6M

The next PPS Mega candidate file to be loaded starts at n=3.6M so we'll soon have data on the stats page for those k's. I'm sure we'll be loading that during TdP.

Thanks for the info! I also talked about k=15-99 in my thread Status and strategy for small k values, and now these k appear on the Stats Mega LLR page! Will they start from n=3.32M? /JeppeSN

Message 126873 - Posted: 15 Feb 2019 | 15:27:04 UTC - in response to Message 126452.

[...] We're now arriving at that point and can start testing k=11-1199 with each candidate file having 20K n spans: 3.60M-3.62M, 3.62M-3.64M, etc. At n=4M, k=9 will be added back in. At n=6M, k=5,7 will be added back in. Candidate size will always be increasing.

We will not be going back to the piecemeal approach that prevailed prior to 2013. There were overlaps where candidates were tested more than once and missed ranges that were never tested (but have been now). I had to track all those ranges down and make sure everything had been tested.

I really appreciate PrimeGrid's careful and systematic approach where everything is tested thoroughly (with double-checking) and in order so that no holes are left, and the history is certain so that everything will not have to be done again at a later time because nobody knows what was tested earlier. This is meant as a huge compliment to JimB and others at PrimeGrid.

However, I have thought more about this, and I think it may be unfortunate, in the case of Proth (Mega) Search, to advance all k between 5 and 1199 in the same pace, in the way described by Jim here. The reason is that small k, let us say k<20, are much more attractive to search at a given size (say n=6M, as an example), than large k, such as 1000<k<1200.

The reason why small k are nicer, is that, for each particular kind of divisor test (where one kind could be F(X), or GF(X,6), or xGF(X,5,2), etc.) I believe that the chance the Proth prime divides some number of that kind, is 1/k.

If we stick to the plan sketched by Jim here, I am afraid searchers outside of PrimeGrid will search "ahead" of us and find the primes before us, for the small k. Hence, the most spectacular (in my opinion) Proth prime finds will be done outside PrimeGrid.

I believe this is already happening today. The following Proth primes with small k (almost certain to be divisors of "something") have been found outside PrimeGrid in a region that our leading edge has not arrived at yet:

I do not know how to "solve" this issue.

I believe low k values should be ahead of intermediate k values which should themselves be ahead of high k values, somehow. But it creates a problem if a single PrimeGrid project has tasks of vastly different sizes at any one point in time. So what do you think?

For k=3, we have a nice soultion with (the plus-form part of) the 321 project. But what about k=5, or k=11? Must they wait for multipliers like k=1199 or k=1173? I think the prioritization should be different, but I do not know what the best way to achieved that would be.

I hope anybody understands what I mean. It is a little hard to explain.

/JeppeSN

Message 126877 - Posted: 15 Feb 2019 | 16:47:33 UTC - in response to Message 126873.

Me:

PS! The third of these did not have any divisor information in the linked page (Caldwell's Top 5000), but the page http://www.prothsearch.com/GFNfacs.html says it divides an xGF(X,5,2), an xGF(X,7,4) and an xGF(X,10,7), so it is not an exception to my claim that "small" k Proth primes "always" divide "something". /JeppeSN

Message 126880 - Posted: 15 Feb 2019 | 17:32:13 UTC - in response to Message 126873.

JeppeSN wrote:
However, I have thought more about this, and I think it may be unfortunate, in the case of Proth (Mega) Search, to advance all k between 5 and 1199 in the same pace, in the way described by Jim here. The reason is that small k, let us say k<20, are much more attractive to search at a given size (say n=6M, as an example), than large k, such as 1000<k<1200.

Does the data back this up?

Fermat divisors found at PG, by K:

+------+----------+ | k | count(*) | +------+----------+ | 9 | 1 | | 25 | 1 | | 27 | 1 | | 57 | 1 | | 131 | 1 | | 151 | 1 | | 183 | 1 | | 193 | 1 | | 267 | 1 | | 329 | 1 | | 519 | 1 | | 651 | 1 | | 659 | 1 | | 1705 | 1 | | 2145 | 1 | | 3771 | 1 | | 4479 | 1 | | 7333 | 1 | | 7905 | 1 | +------+----------+

We've actually found more Fermat Divisors above 1200 (PPSE range) than we have below 100. Only one was found below 20. That's obviously a very simple metric that ignores a lot of important stuff, but it's not all that clear that we have to be focusing on small k's.

I say this not to shoot down the idea, but rather to start the conversation going.
____________
My lucky number is 75898524288+1

Message 126886 - Posted: 15 Feb 2019 | 18:44:29 UTC - in response to Message 126880.

Does the data back this up?

Fermat divisors [...]

Let p = k*2^n + 1 be some Proth prime (or any prime if we have no restriction on the size of k compared to 2^n). k odd.

The multiplicative group modulo p has order p-1 = k*2^n. Note that:

If the order of the element 2 in the multiplicative group modulo p is a power of two, then p divides one (and only one) Fermat number F(X).

If the order of 2 in that group is not a power of two, then p does not divide any Fermat number.

The said multiplicative group is known to be cyclic of order k*2^n. In the cyclic group of order k*2^n there are 2^n elements whose orders are a power of two. That comprises one k-th of the group elements. If we naïvely assume that 2 is a "random" element in the multiplicative group (of course this cannot be rigorously justified), then the "probability" that it works out, should be (2^n)/(k*2^n) = 1/k.

If this "argument" is not convincing, I shall quote a usual authority here: "The probability of the number k.2n+1 dividing any Fermat number appears to be 1/k." (Caldwell).

/JeppeSN

Message 126891 - Posted: 15 Feb 2019 | 19:04:59 UTC

Let us look at the primes 3*2^n + 1 found here at PrimeGrid. There are four:

3*2^10829346+1 is a Factor of GF(10829343,3)!!!! (115850.450000 seconds) 3*2^10829346+1 is a Factor of GF(10829345,5)!!!! (691868.340000 seconds) 3*2^10829346+1 is a Factor of xGF(10829345,5,3)!!!! (0.010000 seconds) 3*2^10829346+1 is a Factor of xGF(10829342,7,4)!!!! (229822.570000 seconds) 3*2^10829346+1 is a Factor of GF(10829344,8)!!!! (114297.210000 seconds) 3*2^10829346+1 is a Factor of xGF(10829344,8,3)!!!! (229347.040000 seconds) 3*2^10829346+1 is a Factor of xGF(10829345,8,5)!!!! (573466.850000 seconds) 3*2^10829346+1 is a Factor of xGF(10829345,9,5)!!!! (0.010000 seconds) 3*2^10829346+1 is a Factor of xGF(10829344,9,8)!!!! (233739.790000 seconds) 3*2^10829346+1 is a Factor of GF(10829345,11)!!!! (0.010000 seconds) 3*2^10829346+1 is a Factor of xGF(10829345,11,3)!!!! (0.010000 seconds) 3*2^10829346+1 is a Factor of xGF(10829344,11,5)!!!! (229529.690000 seconds) 3*2^10829346+1 is a Factor of xGF(10829345,11,8)!!!! (229529.700000 seconds) 3*2^10829346+1 is a Factor of xGF(10829345,11,9)!!!! (0.000000 seconds) 3*2^10829346+1 is a Factor of xGF(10829343,12,7)!!!! (230807.570000 seconds) 3*2^7033641+1 Divides GF(7033639,3) 3*2^7033641+1 Divides GF(7033639,8) 3*2^7033641+1 Divides xGF(7033640,5,2) 3*2^7033641+1 Divides xGF(7033640,6,5) 3*2^7033641+1 Divides xGF(7033639,7,4) 3*2^7033641+1 Divides xGF(7033637,8,3) 3*2^7033641+1 Divides xGF(7033639,9,8) 3*2^7033641+1 Divides xGF(7033640,10,7) 3*2^7033641+1 Divides xGF(7033640,11,4) 3*2^7033641+1 Divides xGF(7033640,11,7) 3*2^7033641+1 Divides xGF(7033638,11,10) 3*2^7033641+1 Divides xGF(7033638,12,7) 3*2^7033641+1 Divides xGF(7033640,12,11) 3*2^5082306+1 is a Factor of GF(5082303,3) 3*2^5082306+1 is a Factor of GF(5082305,5) 3*2^5082306+1 is a Factor of xGF(5082305,5,3) 3*2^5082306+1 is a Factor of xGF(5082302,7,4) 3*2^5082306+1 is a Factor of GF(5082304,8) 3*2^5082306+1 is a Factor of xGF(5082304,8,3) 3*2^5082306+1 is a Factor of xGF(5082305,8,5) 3*2^5082306+1 is a Factor of xGF(5082305,9,5) 3*2^5082306+1 is a Factor of xGF(5082304,9,8) 3*2^5082306+1 is a Factor of GF(5082305,11) 3*2^5082306+1 is a Factor of xGF(5082305,11,3) 3*2^5082306+1 is a Factor of xGF(5082302,11,5) 3*2^5082306+1 is a Factor of xGF(5082305,11,8) 3*2^5082306+1 is a Factor of xGF(5082305,11,9) 3*2^5082306+1 is a Factor of xGF(5082303,12,7) 3*2^2291610+1 is a Factor of GF(2291607,3) 3*2^2291610+1 is a Factor of GF(2291609,5) 3*2^2291610+1 is a Factor of xGF(2291609,5,3) 3*2^2291610+1 is a Factor of xGF(2291607,7,4) 3*2^2291610+1 is a Factor of GF(2291608,8) 3*2^2291610+1 is a Factor of xGF(2291608,8,3) 3*2^2291610+1 is a Factor of xGF(2291609,8,5) 3*2^2291610+1 is a Factor of xGF(2291609,9,5) 3*2^2291610+1 is a Factor of xGF(2291608,9,8) 3*2^2291610+1 is a Factor of GF(2291608,11) 3*2^2291610+1 is a Factor of xGF(2291608,11,3) 3*2^2291610+1 is a Factor of xGF(2291609,11,5) 3*2^2291610+1 is a Factor of xGF(2291607,11,8) 3*2^2291610+1 is a Factor of xGF(2291608,11,9) 3*2^2291610+1 is a Factor of xGF(2291604,12,7)

See how all four divide many GF and xGF?

It is left to the reader to compare with the primes found with k=1199 (there are seven of them).

If you search for k=5 we see only divisibility for one of the four hits. But that must be simply because the data is missing in the database?

/JeppeSN

EDIT:

It was not too hard to reconstruct the data for those k=5 cases, with OpenPFGW:

5*2^1777515+1 is a Factor of GF(1777511,5)!!!! 5*2^1777515+1 is a Factor of GF(1777514,6)!!!! 5*2^1777515+1 is a Factor of xGF(1777514,6,5)!!!! 5*2^1777515+1 is a Factor of GF(1777514,7)!!!! 5*2^1777515+1 is a Factor of xGF(1777514,7,5)!!!! 5*2^1777515+1 is a Factor of xGF(1777513,7,6)!!!! 5*2^1777515+1 is a Factor of xGF(1777513,9,8)!!!! 5*2^1777515+1 is a Factor of xGF(1777512,11,3)!!!! 5*2^240937+1 is a Factor of GF(240936,3)!!!! 5*2^240937+1 is a Factor of xGF(240932,7,5)!!!! 5*2^240937+1 is a Factor of xGF(240932,8,5)!!!! 5*2^240937+1 is a Factor of xGF(240927,8,7)!!!! 5*2^240937+1 is a Factor of GF(240935,11)!!!! 5*2^240937+1 is a Factor of xGF(240936,11,3)!!!! 5*2^240937+1 is a Factor of xGF(240933,11,9)!!!! 5*2^209787+1 is a Factor of xGF(209786,3,2)!!!! 5*2^209787+1 is a Factor of xGF(209786,7,4)!!!! 5*2^209787+1 is a Factor of xGF(209782,7,6)!!!! 5*2^209787+1 is a Factor of xGF(209784,8,5)!!!! 5*2^209787+1 is a Factor of xGF(209786,9,7)!!!! 5*2^209787+1 is a Factor of xGF(209785,11,5)!!!! 5*2^209787+1 is a Factor of xGF(209785,11,8)!!!! 5*2^209787+1 is a Factor of xGF(209786,12,5)!!!! 5*2^209787+1 is a Factor of xGF(209786,12,11)!!!! 5*2^125413+1 is a Factor of F125410!!!! 5*2^125413+1 is a Factor of GF(125410,5)!!!! 5*2^125413+1 is a Factor of xGF(125409,5,2)!!!! 5*2^125413+1 is a Factor of xGF(125410,5,4)!!!! 5*2^125413+1 is a Factor of xGF(125407,8,5)!!!! 5*2^125413+1 is a Factor of xGF(125411,9,7)!!!! 5*2^125413+1 is a Factor of GF(125408,10)!!!! 5*2^125413+1 is a Factor of GF(125412,11)!!!! 5*2^125413+1 is a Factor of xGF(125412,11,2)!!!! 5*2^125413+1 is a Factor of xGF(125412,11,4)!!!! 5*2^125413+1 is a Factor of xGF(125412,11,5)!!!! 5*2^125413+1 is a Factor of xGF(125412,11,8)!!!! 5*2^125413+1 is a Factor of xGF(125412,11,10)!!!!

The smallest of them divides a genuine Fermat number. Caldwell says it was found in 1995 by Jeffrey Young, see 5*2^125413+1; and http://www.prothsearch.com/fermat.html agrees. Maybe an early case of PrimeGrid coming too late with the test of a Proth number with small k?

Yves Gallot Volunteer developer
Project scientist

Joined: 19 Aug 12
Posts: 779
ID: 164101
Credit: 305,422,075
RAC: 4,243 Message 126895 - Posted: 15 Feb 2019 | 22:32:01 UTC - in response to Message 126886.

If this "argument" is not convincing, I shall quote a usual authority here: "The probability of the number k.2n+1 dividing any Fermat number appears to be 1/k." (Caldwell).

A simple argument is that a Fermat number is a GFN like any other.
Harvey Dubner and Wilfrid Keller proved this result for GFN https://www.ams.org/journals/mcom/1995-64-209/S0025-5718-1995-1270618-1/

In my view, Leonid Durman's diagrams http://www.fermatsearch.org/math.html are convincing.

Message 126902 - Posted: 16 Feb 2019 | 6:58:19 UTC - in response to Message 126895.

If this "argument" is not convincing, I shall quote a usual authority here: "The probability of the number k.2n+1 dividing any Fermat number appears to be 1/k." (Caldwell).

A simple argument is that a Fermat number is a GFN like any other.
Harvey Dubner and Wilfrid Keller proved this result for GFN https://www.ams.org/journals/mcom/1995-64-209/S0025-5718-1995-1270618-1/

In my view, Leonid Durman's diagrams http://www.fermatsearch.org/math.html are convincing.

Thank you. I like the logarithmic k scale:

Summing 1/k over a k interval (or integrating, giving the logarithm), we expect to find approximately equal number of Fermat divisors in each of the intervals 10<k<100, 100<k<1000, 1000<k<10000, and so on.

/JeppeSN

Message boards : Proth Prime Search : Where are PPS mega k=15 to 99?