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?  

JimBHonorary cruncher Send message
Joined: 4 Aug 11 Posts: 916 ID: 107307 Credit: 974,118,817 RAC: 6

PPS Mega started on PRPNet, that's where those lowk candidates were tested. We never felt any great need to DC them. PPS Mega was then n=3.322M3.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=1199 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 allcomplex FMA3 FFT length 200K, Pass1=640, Pass2=320, 4 threads, a = 3
Starting Proth prime test of 101*2^3600003+1
Using allcomplex FMA3 FFT length 256K, Pass1=128, Pass2=2K, 4 threads, a = 3
Starting Proth prime test of 501*2^3600003+1
Using allcomplex FMA3 FFT length 256K, Pass1=128, Pass2=2K, 4 threads, a = 7
Starting Proth prime test of 1199*2^3600003+1
Using allcomplex 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 allcomplex FMA3 FFT length 256K, Pass1=128, Pass2=2K, 4 threads, a = 11
Starting Proth prime test of 6999*2^3321918+1
Using allcomplex FMA3 FFT length 256K, Pass1=128, Pass2=2K, 4 threads, a = 5
Starting Proth prime test of 9999*2^3321915+1
Using allcomplex 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.  

CrunchiVolunteer tester
Send message
Joined: 25 Nov 09 Posts: 2911 ID: 50683 Credit: 55,992,501 RAC: 5,779

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
____________
314187728^^{131072}+1 GENERALIZED FERMAT :)
93*10^^{1029523}1 REPDIGIT PRIME
31*332^^{367560}+1 CRUS PRIME
Proud member of team Aggie The Pew. Go Aggie!  

JimBHonorary cruncher Send message
Joined: 4 Aug 11 Posts: 916 ID: 107307 Credit: 974,118,817 RAC: 6

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=999 with n values from 3.22M3.6M. When that was finished we moved to the next 100 k's 101299, then 301399, then 401499. We also tested k=11 from 34542263.6M and k=13 from 35135373.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=5011199 (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=111199 with each candidate file having 20K n spans: 3.60M3.62M, 3.62M3.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 12019999 from the PPSE k range. On June 28, 2017 I created PPS candidate files for n values 2.6M3.0M. We're currently running n=2.7M2.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*2^{n}+1 is the same number as 9*2^{n+1}+1. That holds true for all candidates where b=2.  

rogueVolunteer developer
Send message
Joined: 8 Sep 07 Posts: 1194 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 i77700K (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 counterintuitive. So keep this in mind when selecting multithreading for your machine. I'm definately going with t1 on the i77700K.  


PPS Mega started on PRPNet, that's where those lowk candidates were tested. We never felt any great need to DC them. PPS Mega was then n=3.322M3.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=1199 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=1599 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 lowk candidates were tested. We never felt any great need to DC them. PPS Mega was then n=3.322M3.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=1199 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=1599 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=111199 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=111199 with each candidate file having 20K n spans: 3.60M3.62M, 3.62M3.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 doublechecking) 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 plusform 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: 13244 ID: 53948 Credit: 221,856,227 RAC: 47,934

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 75898^{524288}+1
(I am NOT an administrator anymore, so please don't PM me with questions. I can't help.)  


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 p1 = 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 kth 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^{.}2^{n}+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: 561 ID: 164101 Credit: 304,715,793 RAC: 0

If this "argument" is not convincing, I shall quote a usual authority here: "The probability of the number k^{.}2^{n}+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/199564209/S00255718199512706181/
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^{.}2^{n}+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/199564209/S00255718199512706181/
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? 