PrimeGrid
Please visit donation page to help the project cover running costs for this month

Toggle Menu

Join PrimeGrid

Returning Participants

Community

Leader Boards

Results

Other

drummers-lowrise

Advanced search

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

Author Message
Profile MyrskylyhtyProject donor
Avatar
Send message
Joined: 27 Jan 18
Posts: 106
ID: 972376
Credit: 326,658,513
RAC: 685,610
Found 1 prime in the 2019 Tour de Primes321 LLR Sapphire: Earned 20,000,000 credits (40,973,479)Cullen LLR Gold: Earned 500,000 credits (533,200)ESP LLR Gold: Earned 500,000 credits (808,848)Generalized Cullen/Woodall LLR Silver: Earned 100,000 credits (472,570)PPS LLR Turquoise: Earned 5,000,000 credits (5,519,308)PSP LLR Amethyst: Earned 1,000,000 credits (1,379,782)SoB LLR Ruby: Earned 2,000,000 credits (2,203,691)SR5 LLR Amethyst: Earned 1,000,000 credits (1,003,678)SGS LLR Silver: Earned 100,000 credits (128,562)TRP LLR Gold: Earned 500,000 credits (532,445)Woodall LLR Silver: Earned 100,000 credits (380,849)321 Sieve Bronze: Earned 10,000 credits (44,522)Generalized Cullen/Woodall Sieve (suspended) Amethyst: Earned 1,000,000 credits (1,069,231)PPS Sieve Emerald: Earned 50,000,000 credits (61,446,588)AP 26/27 Ruby: Earned 2,000,000 credits (2,494,531)GFN Double Bronze: Earned 100,000,000 credits (122,591,712)PSA Emerald: Earned 50,000,000 credits (85,075,515)
Message 120966 - Posted: 8 Oct 2018 | 12:46:16 UTC
Last modified: 8 Oct 2018 | 12:46:39 UTC

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.

rogue
Volunteer developer
Avatar
Send message
Joined: 8 Sep 07
Posts: 1190
ID: 12001
Credit: 18,565,548
RAC: 0
PPS LLR Bronze: Earned 10,000 credits (31,229)PSA Jade: Earned 10,000,000 credits (18,533,435)
Message 120969 - Posted: 8 Oct 2018 | 15:38:49 UTC

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.

Profile Michael GoetzProject donor
Volunteer moderator
Project administrator
Project scientist
Avatar
Send message
Joined: 21 Jan 10
Posts: 13045
ID: 53948
Credit: 202,861,869
RAC: 94,196
The "Shut up already!" badge:  This loud mouth has mansplained on the forums over 10 thousand times!  Sheesh!!!Discovered the World's First GFN-19 prime!!!Discovered 1 mega primeFound 1 prime in the 2018 Tour de PrimesFound 1 prime in the 2019 Tour de Primes321 LLR Ruby: Earned 2,000,000 credits (2,822,730)Cullen LLR Ruby: Earned 2,000,000 credits (2,005,249)ESP LLR Turquoise: Earned 5,000,000 credits (5,009,577)Generalized Cullen/Woodall LLR Ruby: Earned 2,000,000 credits (2,145,754)PPS LLR Turquoise: Earned 5,000,000 credits (9,078,658)PSP LLR Turquoise: Earned 5,000,000 credits (5,065,592)SoB LLR Sapphire: Earned 20,000,000 credits (34,221,148)SR5 LLR Turquoise: Earned 5,000,000 credits (8,293,415)SGS LLR Ruby: Earned 2,000,000 credits (2,014,138)TRP LLR Ruby: Earned 2,000,000 credits (2,737,347)Woodall LLR Ruby: Earned 2,000,000 credits (2,195,123)321 Sieve Turquoise: Earned 5,000,000 credits (5,534,630)Cullen/Woodall Sieve (suspended) Ruby: Earned 2,000,000 credits (4,170,256)Generalized Cullen/Woodall Sieve (suspended) Turquoise: Earned 5,000,000 credits (5,059,304)PPS Sieve Sapphire: Earned 20,000,000 credits (20,110,788)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Amethyst: Earned 1,000,000 credits (1,035,522)TRP Sieve (suspended) Ruby: Earned 2,000,000 credits (2,051,121)AP 26/27 Jade: Earned 10,000,000 credits (10,114,260)GFN Emerald: Earned 50,000,000 credits (66,792,810)PSA Jade: Earned 10,000,000 credits (12,404,447)
Message 120970 - Posted: 8 Oct 2018 | 15:50:10 UTC - in response to Message 120969.

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.)


____________
Please do not PM me with support questions. Ask on the forums instead. Thank you!

My lucky number is 75898524288+1

Yves Gallot
Volunteer developer
Project scientist
Send message
Joined: 19 Aug 12
Posts: 524
ID: 164101
Credit: 304,715,793
RAC: 9,349
GFN Double Silver: Earned 200,000,000 credits (304,715,793)
Message 120971 - Posted: 8 Oct 2018 | 15:50:30 UTC - in response to Message 120966.

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.

Profile MyrskylyhtyProject donor
Avatar
Send message
Joined: 27 Jan 18
Posts: 106
ID: 972376
Credit: 326,658,513
RAC: 685,610
Found 1 prime in the 2019 Tour de Primes321 LLR Sapphire: Earned 20,000,000 credits (40,973,479)Cullen LLR Gold: Earned 500,000 credits (533,200)ESP LLR Gold: Earned 500,000 credits (808,848)Generalized Cullen/Woodall LLR Silver: Earned 100,000 credits (472,570)PPS LLR Turquoise: Earned 5,000,000 credits (5,519,308)PSP LLR Amethyst: Earned 1,000,000 credits (1,379,782)SoB LLR Ruby: Earned 2,000,000 credits (2,203,691)SR5 LLR Amethyst: Earned 1,000,000 credits (1,003,678)SGS LLR Silver: Earned 100,000 credits (128,562)TRP LLR Gold: Earned 500,000 credits (532,445)Woodall LLR Silver: Earned 100,000 credits (380,849)321 Sieve Bronze: Earned 10,000 credits (44,522)Generalized Cullen/Woodall Sieve (suspended) Amethyst: Earned 1,000,000 credits (1,069,231)PPS Sieve Emerald: Earned 50,000,000 credits (61,446,588)AP 26/27 Ruby: Earned 2,000,000 credits (2,494,531)GFN Double Bronze: Earned 100,000,000 credits (122,591,712)PSA Emerald: Earned 50,000,000 credits (85,075,515)
Message 120972 - Posted: 8 Oct 2018 | 16:45:57 UTC - in response to Message 120971.
Last modified: 8 Oct 2018 | 16:55:38 UTC

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 BrownProject donor
Volunteer moderator
Project administrator
Volunteer tester
Project scientist
Avatar
Send message
Joined: 17 Oct 05
Posts: 1943
ID: 1178
Credit: 6,600,024,120
RAC: 3,267,351
Discovered the World's First base 116 Generalized Cullen prime!!!Discovered 17 mega primesEliminated 7 conjecture "k"sDiscovered 1 Sophie Germain pairDiscovered 1 Fermat divisor2012 Tour de Primes highest prime count2012 Tour de Primes most Mountain Stage primes2015 Tour de Primes highest prime count2016 Tour de Primes highest prime countFound 23 primes in the 2018 Tour de PrimesFound 1 mega prime in the 2018 Tour de PrimesFound 2 primes in the 2018 Tour de Primes Mountain Stage2019 Tour de Primes highest prime countFound 22 primes in the 2019 Tour de Primes321 LLR Double Bronze: Earned 100,000,000 credits (110,931,288)Cullen LLR Double Bronze: Earned 100,000,000 credits (103,870,990)ESP LLR Double Bronze: Earned 100,000,000 credits (137,499,413)Generalized Cullen/Woodall LLR Double Bronze: Earned 100,000,000 credits (108,461,080)PPS LLR Double Silver: Earned 200,000,000 credits (424,902,380)PSP LLR Double Bronze: Earned 100,000,000 credits (126,275,105)SoB LLR Double Bronze: Earned 100,000,000 credits (135,747,083)SR5 LLR Double Silver: Earned 200,000,000 credits (201,224,339)SGS LLR Double Bronze: Earned 100,000,000 credits (162,297,138)TPS LLR (retired) Silver: Earned 100,000 credits (235,439)TRP LLR Double Bronze: Earned 100,000,000 credits (121,443,822)Woodall LLR Double Bronze: Earned 100,000,000 credits (101,447,725)321 Sieve Double Silver: Earned 200,000,000 credits (203,510,966)Cullen/Woodall Sieve (suspended) Emerald: Earned 50,000,000 credits (83,794,448)Generalized Cullen/Woodall Sieve (suspended) Double Silver: Earned 200,000,000 credits (285,139,652)PPS Sieve Double Ruby: Earned 2,000,000,000 credits (2,124,334,289)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Double Silver: Earned 200,000,000 credits (203,523,358)TRP Sieve (suspended) Double Silver: Earned 200,000,000 credits (201,489,157)AP 26/27 Double Bronze: Earned 100,000,000 credits (135,790,733)GFN Double Amethyst: Earned 1,000,000,000 credits (1,369,059,922)PSA Double Silver: Earned 200,000,000 credits (259,058,048)
Message 120973 - Posted: 8 Oct 2018 | 18:30:45 UTC - in response to Message 120972.


...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.



Profile JeppeSNProject donor
Send message
Joined: 5 Apr 14
Posts: 972
ID: 306875
Credit: 11,517,417
RAC: 8,824
321 LLR Silver: Earned 100,000 credits (360,928)Cullen LLR Bronze: Earned 10,000 credits (98,851)ESP LLR Silver: Earned 100,000 credits (139,922)Generalized Cullen/Woodall LLR Bronze: Earned 10,000 credits (35,236)PPS LLR Ruby: Earned 2,000,000 credits (2,486,479)PSP LLR Silver: Earned 100,000 credits (212,242)SoB LLR Silver: Earned 100,000 credits (237,390)SR5 LLR Bronze: Earned 10,000 credits (16,010)SGS LLR Bronze: Earned 10,000 credits (32,729)TRP LLR Bronze: Earned 10,000 credits (71,060)Woodall LLR Silver: Earned 100,000 credits (109,455)321 Sieve Silver: Earned 100,000 credits (101,851)PSA Turquoise: Earned 5,000,000 credits (7,614,290)
Message 120974 - Posted: 8 Oct 2018 | 19:23:11 UTC - in response to Message 120966.
Last modified: 8 Oct 2018 | 19:23:57 UTC

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

Profile Michael GoetzProject donor
Volunteer moderator
Project administrator
Project scientist
Avatar
Send message
Joined: 21 Jan 10
Posts: 13045
ID: 53948
Credit: 202,861,869
RAC: 94,196
The "Shut up already!" badge:  This loud mouth has mansplained on the forums over 10 thousand times!  Sheesh!!!Discovered the World's First GFN-19 prime!!!Discovered 1 mega primeFound 1 prime in the 2018 Tour de PrimesFound 1 prime in the 2019 Tour de Primes321 LLR Ruby: Earned 2,000,000 credits (2,822,730)Cullen LLR Ruby: Earned 2,000,000 credits (2,005,249)ESP LLR Turquoise: Earned 5,000,000 credits (5,009,577)Generalized Cullen/Woodall LLR Ruby: Earned 2,000,000 credits (2,145,754)PPS LLR Turquoise: Earned 5,000,000 credits (9,078,658)PSP LLR Turquoise: Earned 5,000,000 credits (5,065,592)SoB LLR Sapphire: Earned 20,000,000 credits (34,221,148)SR5 LLR Turquoise: Earned 5,000,000 credits (8,293,415)SGS LLR Ruby: Earned 2,000,000 credits (2,014,138)TRP LLR Ruby: Earned 2,000,000 credits (2,737,347)Woodall LLR Ruby: Earned 2,000,000 credits (2,195,123)321 Sieve Turquoise: Earned 5,000,000 credits (5,534,630)Cullen/Woodall Sieve (suspended) Ruby: Earned 2,000,000 credits (4,170,256)Generalized Cullen/Woodall Sieve (suspended) Turquoise: Earned 5,000,000 credits (5,059,304)PPS Sieve Sapphire: Earned 20,000,000 credits (20,110,788)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Amethyst: Earned 1,000,000 credits (1,035,522)TRP Sieve (suspended) Ruby: Earned 2,000,000 credits (2,051,121)AP 26/27 Jade: Earned 10,000,000 credits (10,114,260)GFN Emerald: Earned 50,000,000 credits (66,792,810)PSA Jade: Earned 10,000,000 credits (12,404,447)
Message 120975 - Posted: 8 Oct 2018 | 20:03:28 UTC - in response to Message 120974.

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)
____________
Please do not PM me with support questions. Ask on the forums instead. Thank you!

My lucky number is 75898524288+1

Yves Gallot
Volunteer developer
Project scientist
Send message
Joined: 19 Aug 12
Posts: 524
ID: 164101
Credit: 304,715,793
RAC: 9,349
GFN Double Silver: Earned 200,000,000 credits (304,715,793)
Message 120977 - Posted: 8 Oct 2018 | 21:39:28 UTC - in response to Message 120975.

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 zero-padding).
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/2003-72-241/S0025-5718-02-01419-9/
I think that llr implements Colin Percival's algorithm.

Profile JeppeSNProject donor
Send message
Joined: 5 Apr 14
Posts: 972
ID: 306875
Credit: 11,517,417
RAC: 8,824
321 LLR Silver: Earned 100,000 credits (360,928)Cullen LLR Bronze: Earned 10,000 credits (98,851)ESP LLR Silver: Earned 100,000 credits (139,922)Generalized Cullen/Woodall LLR Bronze: Earned 10,000 credits (35,236)PPS LLR Ruby: Earned 2,000,000 credits (2,486,479)PSP LLR Silver: Earned 100,000 credits (212,242)SoB LLR Silver: Earned 100,000 credits (237,390)SR5 LLR Bronze: Earned 10,000 credits (16,010)SGS LLR Bronze: Earned 10,000 credits (32,729)TRP LLR Bronze: Earned 10,000 credits (71,060)Woodall LLR Silver: Earned 100,000 credits (109,455)321 Sieve Silver: Earned 100,000 credits (101,851)PSA Turquoise: Earned 5,000,000 credits (7,614,290)
Message 120978 - Posted: 8 Oct 2018 | 22:13:30 UTC

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 3-smooth.

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 Gallot
Volunteer developer
Project scientist
Send message
Joined: 19 Aug 12
Posts: 524
ID: 164101
Credit: 304,715,793
RAC: 9,349
GFN Double Silver: Earned 200,000,000 credits (304,715,793)
Message 120979 - Posted: 8 Oct 2018 | 22:17:19 UTC - in response to Message 120972.

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 Gallot
Volunteer developer
Project scientist
Send message
Joined: 19 Aug 12
Posts: 524
ID: 164101
Credit: 304,715,793
RAC: 9,349
GFN Double Silver: Earned 200,000,000 credits (304,715,793)
Message 120982 - Posted: 9 Oct 2018 | 9:54:13 UTC - in response to Message 120979.

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.pagesperso-orange.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?

[Return to PrimeGrid main page]
DNS Powered by DNSEXIT.COM
Copyright © 2005 - 2019 Rytis Slatkevičius (contact) and PrimeGrid community. Server load 2.67, 2.62, 2.64
Generated 11 Dec 2019 | 9:13:05 UTC