Join PrimeGrid
Returning Participants
Community
Leader Boards
Results
Other
drummerslowrise

Message boards :
Proth Prime Search :
Would excluding k's be a good idea in the future?
Author 
Message 

It is a well known fact that some k's are just better than others for finding Proth Primes.
Some k's are easier to sieve, leading to a low tasks/prime ratio (k=607, 739, 395, 1307, 5387, ...)
Some k's just have a lot of primes, which means it is desirable to test them (k=165, 1023, 435, 975, 8499, 4257, 9867, ...)
And some k's just dont seem to produce much primes at all (k = 31, 47, 167, 1899, any k from SoB, ...)
(Above k's based mostly only on Primegrid's statistics)
((And some k's are just monsters! https://groups.yahoo.com/neo/groups/primenumbers/conversations/topics/9963))
Also we have the fact, that smaller k's are noticeably faster to test.
So I ask; would it be feasible/efficient to make the PPS project a little more focused some time in the future? We wouldnt keep testing the k's in SoB either (actually some old SoB k's apparently ARE in PPSE), so why should we spend our time and electricity on k's that dont are not efficient in finding primes? We would of course lose some of sieving work, although nothing stops us from testing the more undesirable k's at some later point if we want.
Currently since we are sieving PPS already to 9M, we would still have work left for years to come, even if we dont test every k.
Some discussion related to this topic was also in this topic: http://www.primegrid.com/forum_thread.php?id=8029.
What do you think? Currently we have 10 k's in PPS and 404 k's in PPSE with no primes. Average number of primes per k is 7.87 in PPS and 3.80 in PPSE.  

rogueVolunteer developer
Send message
Joined: 8 Sep 07 Posts: 1249 ID: 12001 Credit: 18,565,548 RAC: 0

Is it feasable? Probably. Is it desirable? Probably not.
One of the stated goals of PPS/PPSE is to search all k < 10,000. Such a change would be in conflict with that goal.
I do agree that if a k was tested by SoB, then those residues could be imported to PPS/PPSE so that the n for those k that have already been tested can be skipped.  

Michael GoetzVolunteer moderator Project administrator
Send message
Joined: 21 Jan 10 Posts: 13804 ID: 53948 Credit: 345,369,032 RAC: 6,456

I do agree that if a k was tested by SoB, then those residues could be imported to PPS/PPSE so that the n for those k that have already been tested can be skipped.
Those residues are lost. PrimeGrid never had them, and all of SoB's data is lost.
Perhaps some members may have some in their logs, but it would be a lot of work for us to use them in PPS/PPSE since those are not compatible with the normal way we run LLR. It would take a lot of effort for a very tiny amount of savings. So even if you have some of those residues, don't send them to me. We wouldn't use them. (And DEFINITELY don't insert them into our residue system  that will hurt, not help.)
____________
My lucky number is 75898^{524288}+1  

Yves GallotVolunteer developer Project scientist Send message
Joined: 19 Aug 12 Posts: 712 ID: 164101 Credit: 305,166,630 RAC: 0

It is a well known fact that some k's are just better than others for finding Proth Primes.
No, because after sieving all k's are equal.
Some k's just have a lot of primes, which means it is desirable to test them (k=165, 1023, 435, 975, 8499, 4257, 9867, ...)
They have also a lot of candidates. The ratio #primes/#candidates is constant for a fixed sieve limit.
 


It is a well known fact that some k's are just better than others for finding Proth Primes.
No, because after sieving all k's are equal.
Some k's just have a lot of primes, which means it is desirable to test them (k=165, 1023, 435, 975, 8499, 4257, 9867, ...)
They have also a lot of candidates. The ratio #primes/#candidates is constant for a fixed sieve limit.
Really? I previously thought that different k's fared differently because of how they get factored, with sierpinski numbers being the extreme case.
So, are the remaining SoB candidates still unsolved just because of randomness? Same question goes for #primes/#candidates in PPS; k=607 has #primes/#candidates = 11/39841 = 0.000276097, while k=839 has #primes/#candidates = 0/46307 = 0, is this just by randomness? Should the SoB candidates theoritically really have the same density as any other k other than sierpinski, and they are just the extreme end of a distribution.
Would even the SoB candidates converge to a similar efficiency as any other k in the end?
I guess I've totally misunderstood, and have a lot to learn then.  

Scott BrownVolunteer moderator Project administrator Volunteer tester Project scientist
Send message
Joined: 17 Oct 05 Posts: 2329 ID: 1178 Credit: 15,572,998,840 RAC: 16,577,710

...Same question goes for #primes/#candidates in PPS; k=607 has #primes/#candidates = 11/39841 = 0.000276097, while k=839 has #primes/#candidates = 0/46307 = 0, is this just by randomness?...
I guess I've totally misunderstood, and have a lot to learn then.
I think you are considering this more with a mathematical point of view rather than a statistical one. A statistician wouldn't blink at an 11 out of 40,000 vs. 0 out of 40,000 difference in a standard model. Indeed, it wouldn't be unlikely that random draws from the same distribution (remember that those primes come from an infinite distribution) would obtain each of those results. This is an issue known for statistical conclusions when dealing with extraordinarily rare events (I don't have the statistical work that explains this at my fingertips, but they should be readily found in an online search), and as I understand it is especially the case when the rare events are independent.
 


I think it makes sense to search all odd k in parallel. Sure enough, some k will have more candidates after sieving, so we will spend relatively more time with them, but also find more primes there. That should be proportional to the effort spent. Yves already explained it better.
You could search only the k values with many candidates, but why not include the others, for a little extra work?
In the opposite direction, you could also search only the k values with few candidates, from the consideration that their primes are more "valuable" because in some sense they are rarer. In fact, this is what we do with SoB. Of course the disadvantage with this is that there are few candidates in each n interval (exponent interval), so the n value goes up really fast if you focus all your ressources on these k with few primes.
Also we have the fact, that smaller k's are noticeably faster to test.
How much faster, and why? I would have thought that smaller k were about the same speed as (somewhat) larger k.
/JeppeSN  

Michael GoetzVolunteer moderator Project administrator
Send message
Joined: 21 Jan 10 Posts: 13804 ID: 53948 Credit: 345,369,032 RAC: 6,456

Also we have the fact, that smaller k's are noticeably faster to test.
How much faster, and why? I would have thought that smaller k were about the same speed as (somewhat) larger k.
/JeppeSN
He's correct, at least when there's a large difference in k. K has an effect on the FFT size, and thus on speed.
That's why 321 is as fast as it is, when compared to projects of similar size. It's a lot faster than Cullen. While it's true that Cullen's numbers are larger, that doesn't account for Cullen numbers taking 3 times as long to test. More telling is ESP, which is testing smaller numbers than 321, yet takes longer to test.
321's FFT size is 768K (4.4 million digits)
ESP's FFT sizes are 1152K and 1280K, despite the numbers being smaller. (3.7 million digits)
Cullen's FFT sizes range from 1280K to 1792K (5.1 million digits)
____________
My lucky number is 75898^{524288}+1  

Yves GallotVolunteer developer Project scientist Send message
Joined: 19 Aug 12 Posts: 712 ID: 164101 Credit: 305,166,630 RAC: 0

He's correct, at least when there's a large difference in k. K has an effect on the FFT size, and thus on speed.
That's why 321 is as fast as it is, when compared to projects of similar size. It's a lot faster than Cullen. While it's true that Cullen's numbers are larger, that doesn't account for Cullen numbers taking 3 times as long to test. More telling is ESP, which is testing smaller numbers than 321, yet takes longer to test.
321's FFT size is 768K (4.4 million digits)
ESP's FFT sizes are 1152K and 1280K, despite the numbers being smaller. (3.7 million digits)
Cullen's FFT sizes range from 1280K to 1792K (5.1 million digits)
Richard Crandall and Barry Fagin indicated how to use the Discrete Weighted Transform for performing integer multiplication modulo Mersenne or Fermat numbers with a half FFT size (without zeropadding).
I extended the method to GFN (but today genefer is based on a different transform).
Colin Percival found how to extend DWT to the form k.2^nÂ±1 when k is "small".
http://www.ams.org/journals/mcom/200372241/S0025571802014199/
I think that llr implements Colin Percival's algorithm.
 


Ah, I do not know so much about how these calculations are done, but one can learn from reading these threads.
What happens if we compare, as an example, k=6553 and k=6561, for similar values of n? Because 6553 is "rough" (it is a prime), while 6561, despite being slightly larger, is 3smooth.
Is 6561*2^n + 1 in fact just as efficient af 3*2^n + 1?
Should we prefer smooth k and skip rough k?
/JeppeSN  

Yves GallotVolunteer developer Project scientist Send message
Joined: 19 Aug 12 Posts: 712 ID: 164101 Credit: 305,166,630 RAC: 0

Would even the SoB candidates converge to a similar efficiency as any other k in the end?
Yes, this is a conjecture. Today no statistical deviation was found to disprove it.
 

Yves GallotVolunteer developer Project scientist Send message
Joined: 19 Aug 12 Posts: 712 ID: 164101 Credit: 305,166,630 RAC: 0

Would even the SoB candidates converge to a similar efficiency as any other k in the end?
Yes, this is a conjecture. Today no statistical deviation was found to disprove it.
I wrote a note about "The number of primes in a sequence" in 2001.
http://yves.gallot.pagespersoorange.fr/papers/weight.pdf
The estimate of the weight is similar to the amount of candidates after sieving.
The Batemanâ€“Horn conjecture can be checked because polynomials don't grow too quickly. Today the GFPS is a strong verification of the conjecture with some large exponents.
But because 2^n is an exponential, the density of primes fall off quite rapidly = O(log(n)). It is hard to find a deviation with small numbers. Statistics are based on the law of large numbers...  

Message boards :
Proth Prime Search :
Would excluding k's be a good idea in the future? 