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 : Where are PPS mega k=15 to 99?

Author Message
Profile MyrskylyhtyProject donor
Avatar
Send message
Joined: 27 Jan 18
Posts: 103
ID: 972376
Credit: 295,621,204
RAC: 447,896
Found 1 prime in the 2019 Tour de Primes321 LLR Sapphire: Earned 20,000,000 credits (36,734,184)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,501,947)PSP LLR Gold: Earned 500,000 credits (719,124)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 (43,302)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 Emerald: Earned 50,000,000 credits (96,473,938)PSA Emerald: Earned 50,000,000 credits (85,075,515)
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?

JimBProject donor
Volunteer moderator
Project administrator
Project developer
Send message
Joined: 4 Aug 11
Posts: 884
ID: 107307
Credit: 852,078,271
RAC: 125,378
321 LLR Ruby: Earned 2,000,000 credits (2,071,006)Cullen LLR Ruby: Earned 2,000,000 credits (4,831,475)ESP LLR Turquoise: Earned 5,000,000 credits (5,064,082)Generalized Cullen/Woodall LLR Ruby: Earned 2,000,000 credits (2,589,971)PPS LLR Ruby: Earned 2,000,000 credits (2,668,927)PSP LLR Turquoise: Earned 5,000,000 credits (5,013,650)SoB LLR Sapphire: Earned 20,000,000 credits (42,020,807)SR5 LLR Jade: Earned 10,000,000 credits (10,987,079)SGS LLR Ruby: Earned 2,000,000 credits (2,069,865)TRP LLR Ruby: Earned 2,000,000 credits (2,145,683)Woodall LLR Ruby: Earned 2,000,000 credits (2,595,228)321 Sieve Turquoise: Earned 5,000,000 credits (5,606,063)Cullen/Woodall Sieve (suspended) Ruby: Earned 2,000,000 credits (4,002,919)Generalized Cullen/Woodall Sieve (suspended) Sapphire: Earned 20,000,000 credits (20,005,451)PPS Sieve Emerald: Earned 50,000,000 credits (50,809,179)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Ruby: Earned 2,000,000 credits (2,341,676)TRP Sieve (suspended) Ruby: Earned 2,000,000 credits (2,070,804)AP 26/27 Jade: Earned 10,000,000 credits (10,742,251)GFN Sapphire: Earned 20,000,000 credits (31,494,612)PSA Double Gold: Earned 500,000,000 credits (642,948,763)
Message 126423 - Posted: 7 Feb 2019 | 9:08:55 UTC - in response to Message 126422.
Last modified: 7 Feb 2019 | 9:09:37 UTC

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.

Chara34122
Send message
Joined: 11 Feb 17
Posts: 43
ID: 490242
Credit: 7,005,040
RAC: 4,136
321 LLR Bronze: Earned 10,000 credits (93,702)Cullen LLR Silver: Earned 100,000 credits (106,188)ESP LLR Silver: Earned 100,000 credits (204,764)Generalized Cullen/Woodall LLR Silver: Earned 100,000 credits (107,884)PPS LLR Silver: Earned 100,000 credits (242,043)PSP LLR Silver: Earned 100,000 credits (200,302)SoB LLR Ruby: Earned 2,000,000 credits (2,128,114)SR5 LLR Bronze: Earned 10,000 credits (41,760)SGS LLR Silver: Earned 100,000 credits (159,894)TRP LLR Silver: Earned 100,000 credits (240,082)Woodall LLR Bronze: Earned 10,000 credits (36,435)321 Sieve Gold: Earned 500,000 credits (751,988)Generalized Cullen/Woodall Sieve (suspended) Ruby: Earned 2,000,000 credits (2,000,299)PPS Sieve Bronze: Earned 10,000 credits (47,194)AP 26/27 Bronze: Earned 10,000 credits (97,032)GFN Silver: Earned 100,000 credits (297,213)PSA Silver: Earned 100,000 credits (244,860)
Message 126425 - Posted: 7 Feb 2019 | 9:45:29 UTC - in response to Message 126423.
Last modified: 7 Feb 2019 | 9:47:31 UTC

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

Profile MyrskylyhtyProject donor
Avatar
Send message
Joined: 27 Jan 18
Posts: 103
ID: 972376
Credit: 295,621,204
RAC: 447,896
Found 1 prime in the 2019 Tour de Primes321 LLR Sapphire: Earned 20,000,000 credits (36,734,184)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,501,947)PSP LLR Gold: Earned 500,000 credits (719,124)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 (43,302)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 Emerald: Earned 50,000,000 credits (96,473,938)PSA Emerald: Earned 50,000,000 credits (85,075,515)
Message 126426 - Posted: 7 Feb 2019 | 10:16:10 UTC - in response to Message 126425.
Last modified: 7 Feb 2019 | 10:16:58 UTC

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

Profile MyrskylyhtyProject donor
Avatar
Send message
Joined: 27 Jan 18
Posts: 103
ID: 972376
Credit: 295,621,204
RAC: 447,896
Found 1 prime in the 2019 Tour de Primes321 LLR Sapphire: Earned 20,000,000 credits (36,734,184)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,501,947)PSP LLR Gold: Earned 500,000 credits (719,124)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 (43,302)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 Emerald: Earned 50,000,000 credits (96,473,938)PSA Emerald: Earned 50,000,000 credits (85,075,515)
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.

Profile Crun-chiProject donor
Volunteer tester
Avatar
Send message
Joined: 25 Nov 09
Posts: 2785
ID: 50683
Credit: 52,558,486
RAC: 770
Eliminated 1 conjecture "k"Found 1 prime in the 2018 Tour de PrimesFound 1 prime in the 2019 Tour de Primes321 LLR Silver: Earned 100,000 credits (229,492)Cullen LLR Silver: Earned 100,000 credits (110,733)PPS LLR Ruby: Earned 2,000,000 credits (2,982,840)PSP LLR Silver: Earned 100,000 credits (104,385)SoB LLR Silver: Earned 100,000 credits (106,117)SR5 LLR Silver: Earned 100,000 credits (139,802)SGS LLR Amethyst: Earned 1,000,000 credits (1,073,792)TRP LLR Silver: Earned 100,000 credits (122,712)Woodall LLR Silver: Earned 100,000 credits (122,944)321 Sieve Silver: Earned 100,000 credits (104,900)Cullen/Woodall Sieve (suspended) Ruby: Earned 2,000,000 credits (2,000,599)Generalized Cullen/Woodall Sieve (suspended) Gold: Earned 500,000 credits (515,556)PPS Sieve Jade: Earned 10,000,000 credits (11,343,583)TRP Sieve (suspended) Silver: Earned 100,000 credits (255,612)AP 26/27 Ruby: Earned 2,000,000 credits (2,575,874)GFN Sapphire: Earned 20,000,000 credits (23,247,434)PSA Turquoise: Earned 5,000,000 credits (7,522,050)
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
____________
271643232^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!

JimBProject donor
Volunteer moderator
Project administrator
Project developer
Send message
Joined: 4 Aug 11
Posts: 884
ID: 107307
Credit: 852,078,271
RAC: 125,378
321 LLR Ruby: Earned 2,000,000 credits (2,071,006)Cullen LLR Ruby: Earned 2,000,000 credits (4,831,475)ESP LLR Turquoise: Earned 5,000,000 credits (5,064,082)Generalized Cullen/Woodall LLR Ruby: Earned 2,000,000 credits (2,589,971)PPS LLR Ruby: Earned 2,000,000 credits (2,668,927)PSP LLR Turquoise: Earned 5,000,000 credits (5,013,650)SoB LLR Sapphire: Earned 20,000,000 credits (42,020,807)SR5 LLR Jade: Earned 10,000,000 credits (10,987,079)SGS LLR Ruby: Earned 2,000,000 credits (2,069,865)TRP LLR Ruby: Earned 2,000,000 credits (2,145,683)Woodall LLR Ruby: Earned 2,000,000 credits (2,595,228)321 Sieve Turquoise: Earned 5,000,000 credits (5,606,063)Cullen/Woodall Sieve (suspended) Ruby: Earned 2,000,000 credits (4,002,919)Generalized Cullen/Woodall Sieve (suspended) Sapphire: Earned 20,000,000 credits (20,005,451)PPS Sieve Emerald: Earned 50,000,000 credits (50,809,179)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Ruby: Earned 2,000,000 credits (2,341,676)TRP Sieve (suspended) Ruby: Earned 2,000,000 credits (2,070,804)AP 26/27 Jade: Earned 10,000,000 credits (10,742,251)GFN Sapphire: Earned 20,000,000 credits (31,494,612)PSA Double Gold: Earned 500,000,000 credits (642,948,763)
Message 126452 - Posted: 7 Feb 2019 | 15:00:42 UTC - in response to Message 126426.
Last modified: 7 Feb 2019 | 15:01:38 UTC

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
Avatar
Send message
Joined: 8 Sep 07
Posts: 1188
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 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.

Profile MyrskylyhtyProject donor
Avatar
Send message
Joined: 27 Jan 18
Posts: 103
ID: 972376
Credit: 295,621,204
RAC: 447,896
Found 1 prime in the 2019 Tour de Primes321 LLR Sapphire: Earned 20,000,000 credits (36,734,184)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,501,947)PSP LLR Gold: Earned 500,000 credits (719,124)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 (43,302)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 Emerald: Earned 50,000,000 credits (96,473,938)PSA Emerald: Earned 50,000,000 credits (85,075,515)
Message 126509 - Posted: 8 Feb 2019 | 9:08:38 UTC
Last modified: 8 Feb 2019 | 9:10:23 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.

Profile JeppeSNProject donor
Send message
Joined: 5 Apr 14
Posts: 946
ID: 306875
Credit: 11,033,882
RAC: 7,943
321 LLR Silver: Earned 100,000 credits (285,114)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,424,942)SoB LLR Silver: Earned 100,000 credits (237,390)SR5 LLR Bronze: Earned 10,000 credits (16,010)TRP LLR Bronze: Earned 10,000 credits (71,060)Woodall LLR Silver: Earned 100,000 credits (109,455)PSA Turquoise: Earned 5,000,000 credits (7,614,290)
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

Profile MyrskylyhtyProject donor
Avatar
Send message
Joined: 27 Jan 18
Posts: 103
ID: 972376
Credit: 295,621,204
RAC: 447,896
Found 1 prime in the 2019 Tour de Primes321 LLR Sapphire: Earned 20,000,000 credits (36,734,184)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,501,947)PSP LLR Gold: Earned 500,000 credits (719,124)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 (43,302)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 Emerald: Earned 50,000,000 credits (96,473,938)PSA Emerald: Earned 50,000,000 credits (85,075,515)
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


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"

Profile JeppeSNProject donor
Send message
Joined: 5 Apr 14
Posts: 946
ID: 306875
Credit: 11,033,882
RAC: 7,943
321 LLR Silver: Earned 100,000 credits (285,114)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,424,942)SoB LLR Silver: Earned 100,000 credits (237,390)SR5 LLR Bronze: Earned 10,000 credits (16,010)TRP LLR Bronze: Earned 10,000 credits (71,060)Woodall LLR Silver: Earned 100,000 credits (109,455)PSA Turquoise: Earned 5,000,000 credits (7,614,290)
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

Profile JeppeSNProject donor
Send message
Joined: 5 Apr 14
Posts: 946
ID: 306875
Credit: 11,033,882
RAC: 7,943
321 LLR Silver: Earned 100,000 credits (285,114)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,424,942)SoB LLR Silver: Earned 100,000 credits (237,390)SR5 LLR Bronze: Earned 10,000 credits (16,010)TRP LLR Bronze: Earned 10,000 credits (71,060)Woodall LLR Silver: Earned 100,000 credits (109,455)PSA Turquoise: Earned 5,000,000 credits (7,614,290)
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

Profile Michael GoetzProject donor
Volunteer moderator
Project administrator
Project scientist
Avatar
Send message
Joined: 21 Jan 10
Posts: 12941
ID: 53948
Credit: 195,734,145
RAC: 153,215
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,085,897)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 (6,798,385)PSP LLR Ruby: Earned 2,000,000 credits (2,632,269)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,012,222)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,046,112)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 (65,610,884)PSA Jade: Earned 10,000,000 credits (12,404,447)
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.
____________
Please do not PM me with support questions. Ask on the forums instead. Thank you!

My lucky number is 75898524288+1

Profile JeppeSNProject donor
Send message
Joined: 5 Apr 14
Posts: 946
ID: 306875
Credit: 11,033,882
RAC: 7,943
321 LLR Silver: Earned 100,000 credits (285,114)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,424,942)SoB LLR Silver: Earned 100,000 credits (237,390)SR5 LLR Bronze: Earned 10,000 credits (16,010)TRP LLR Bronze: Earned 10,000 credits (71,060)Woodall LLR Silver: Earned 100,000 credits (109,455)PSA Turquoise: Earned 5,000,000 credits (7,614,290)
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

Profile JeppeSNProject donor
Send message
Joined: 5 Apr 14
Posts: 946
ID: 306875
Credit: 11,033,882
RAC: 7,943
321 LLR Silver: Earned 100,000 credits (285,114)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,424,942)SoB LLR Silver: Earned 100,000 credits (237,390)SR5 LLR Bronze: Earned 10,000 credits (16,010)TRP LLR Bronze: Earned 10,000 credits (71,060)Woodall LLR Silver: Earned 100,000 credits (109,455)PSA Turquoise: Earned 5,000,000 credits (7,614,290)
Message 126891 - Posted: 15 Feb 2019 | 19:04:59 UTC
Last modified: 15 Feb 2019 | 19:44:18 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
Send message
Joined: 19 Aug 12
Posts: 518
ID: 164101
Credit: 301,703,241
RAC: 175,303
GFN Double Silver: Earned 200,000,000 credits (301,703,241)
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.

Profile JeppeSNProject donor
Send message
Joined: 5 Apr 14
Posts: 946
ID: 306875
Credit: 11,033,882
RAC: 7,943
321 LLR Silver: Earned 100,000 credits (285,114)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,424,942)SoB LLR Silver: Earned 100,000 credits (237,390)SR5 LLR Bronze: Earned 10,000 credits (16,010)TRP LLR Bronze: Earned 10,000 credits (71,060)Woodall LLR Silver: Earned 100,000 credits (109,455)PSA Turquoise: Earned 5,000,000 credits (7,614,290)
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

Post to thread

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

[Return to PrimeGrid main page]
DNS Powered by DNSEXIT.COM
Copyright © 2005 - 2019 Rytis Slatkevičius (contact) and PrimeGrid community. Server load 7.22, 6.79, 4.78
Generated 21 Oct 2019 | 16:07:23 UTC