Join PrimeGrid
Returning Participants
Community
Leader Boards
Results
Other
drummers-lowrise
|
Message boards :
Proth Prime Search :
Where are PPS mega k=15 to 99?
| Author |
Message |
|---|
|
|
|
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? | |
|
JimB Honorary cruncher
Send message
Joined: 4 Aug 11
Posts: 918
ID: 107307
Credit: 977,945,376
RAC: 0
                     
|
|
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. | |
|
|
|
|
Next MEGAs are with larger n's? Why not with larger k's? | |
|
|
|
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 :) | |
|
|
|
|
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. | |
|
 Crun-chiVolunteer tester
Send message
Joined: 25 Nov 09
Posts: 3183
ID: 50683
Credit: 112,554,621
RAC: 405,600
                       
|
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! | |
|
JimBHonorary cruncher
Send message
Joined: 4 Aug 11
Posts: 918
ID: 107307
Credit: 977,945,376
RAC: 0
|
|
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. | |
|
rogueVolunteer developer
Send message
Joined: 8 Sep 07
Posts: 1255
ID: 12001
Credit: 18,565,548
RAC: 0
 
|
|
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. | |
|
|
|
|
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. | |
|
|
|
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 | |
|
|
|
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
From your linked thread: "k=11-1199 will start being tested in MEGA at n=3.6M+ the next time we need to load work there" | |
|
|
|
[...] 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
| |
|
|
|
|
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 | |
|
Michael GoetzVolunteer moderator
Project administrator
Send message
Joined: 21 Jan 10
Posts: 13881
ID: 53948
Credit: 383,616,269
RAC: 119,450
             
|
|
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 | |
|
|
|
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 | |
|
|
|
|
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 GallotVolunteer developer
Project scientist
Send message
Joined: 19 Aug 12
Posts: 779
ID: 164101
Credit: 305,422,075
RAC: 4,243
|
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.
| |
|
|
|
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? |
