Join PrimeGrid
Returning Participants
Community
Leader Boards
Results
Other
drummers-lowrise
|
Message boards :
Generalized Fermat Prime Search :
GFN1 - GFN12 Status
Author |
Message |
|
Greetings All,
After reading the answers to my recent questions regarding GFN primes and looking at the data analysis provided by Yves for the GFN-13 search, my interest was piqued and I started to look further into the conjecture on Yves' site (http://yves.gallot.pagesperso-orange.fr/primes/stat.htm). I had used the calculator on that page in the past but had not paid much attention to the table Yves posted below it showing the status of the lower GFNs. For GFN2 through GFN12 the maximum b value listed wasn't all that high compared to what I thought possible with newer computers and looking around I couldn't find anywhere that had definitely tested these to a higher b value than was indicated in the table, so I figured that they may have fallen through the cracks into a gap where they were not tested at the time due to lack of available computing power, but now that we have the computing power they are no longer "interesting" to test. There is a forum post from 2009 (http://www.primegrid.com/forum_thread.php?id=1528) which indicates that GFNs 1-4 may have been tested to b=1G and that GFNs 5-12 may have been tested to b=100M, but I could not find the results of that testing and the results are not indicated on the GFN Prime Search Status and History page (http://www.primegrid.com/gfn_history.php) so, in the spirit of Tour de Primes, I decided to embark on my own primes adventure and take GFNs 1-12 to a much higher b value (2G), make the results available, and also to see how well the predicted numbers of primes match the actual numbers.
What I thought would be a relatively quick and simple task proved to be much bigger than anticipated and is certainly still a work in progress, but I figured with GFN6 and GFN7 complete to b=2,000,000,000 and the rest of 1-8 between 40% and 90% complete I would post the GFN6 and GFN7 results with a comparison between predicted and actual prime counts. Everything below is a single-pass over the data tested with LLR (and sieved with AthGfnSv and AthGfn64 v.B306). All primes listed by Yves were found for GFNs 2-7 in my search (I haven't checked 1 and 8 yet), and it appears that none were missed by his search as I have found none not previously listed. It is my plan to update this post with the same data for each of the other GFN n values as the testing is completed. Lists of prime b values for each GFN are available at the link under each table.
The results:
+-----------------------------------------------------------------------------------------------------+
| GFN6 |
+---------------+---------------+--------------+--------------+------------------+--------------------+
| b-min | b-max | Expected (E) | Actual (A) | Difference (A-E) | % Diff (A-E)/E*100 |
+---------------+---------------+--------------+--------------+------------------+--------------------+
| 2 | 99,999,998 | 354983 | 354239 | -744 | -0.210 |
| 100,000,000 | 199,999,998 | 327603 | 327792 | 189 | 0.058 |
| 200,000,000 | 299,999,998 | 318711 | 318823 | 112 | 0.035 |
| 300,000,000 | 399,999,998 | 313200 | 312507 | -693 | -0.221 |
| 400,000,000 | 499,999,998 | 309225 | 310149 | 924 | 0.299 |
| 500,000,000 | 599,999,998 | 306130 | 305410 | -720 | -0.235 |
| 600,000,000 | 699,999,998 | 303603 | 304186 | 583 | 0.192 |
| 700,000,000 | 799,999,998 | 301473 | 302666 | 1193 | 0.396 |
| 800,000,000 | 899,999,998 | 299635 | 299414 | -221 | -0.074 |
| 900,000,000 | 999,999,998 | 298021 | 298482 | 461 | 0.155 |
| 1,000,000,000 | 1,099,999,998 | 296584 | 296606 | 22 | 0.007 |
| 1,100,000,000 | 1,199,999,998 | 295289 | 295492 | 203 | 0.069 |
| 1,200,000,000 | 1,299,999,998 | 294113 | 294426 | 313 | 0.106 |
| 1,300,000,000 | 1,399,999,998 | 293036 | 293500 | 464 | 0.158 |
| 1,400,000,000 | 1,499,999,998 | 292043 | 292909 | 866 | 0.297 |
| 1,500,000,000 | 1,599,999,998 | 291122 | 291093 | -29 | -0.010 |
| 1,600,000,000 | 1,699,999,998 | 290264 | 290698 | 434 | 0.150 |
| 1,700,000,000 | 1,799,999,998 | 289462 | 289542 | 80 | 0.028 |
| 1,800,000,000 | 1,899,999,998 | 288708 | 288935 | 227 | 0.079 |
| 1,900,000,000 | 2,000,000,000 | 287997 | 287679 | -318 | -0.110 |
+---------------+---------------+--------------+--------------+------------------+--------------------+
| 2 | 2,000,000,000 | 6051202 | 6054548 | 3346 | 0.055 |
+---------------+---------------+--------------+--------------+------------------+--------------------+ GFN6 Prime b Values: https://drive.google.com/open?id=1zM7NPdZHUS1YiXZxwHXKWdZwog0psOqC
+-----------------------------------------------------------------------------------------------------+
| GFN7 |
+---------------+---------------+--------------+--------------+------------------+--------------------+
| b-min | b-max | Expected (E) | Actual (A) | Difference (A-E) | % Diff (A-E)/E*100 |
+---------------+---------------+--------------+--------------+------------------+--------------------+
| 2 | 99,999,998 | 139957 | 139921 | -36 | -0.026 |
| 100,000,000 | 199,999,998 | 129162 | 129488 | 326 | 0.252 |
| 200,000,000 | 299,999,998 | 125656 | 125779 | 123 | 0.098 |
| 300,000,000 | 399,999,998 | 123483 | 123168 | -315 | -0.255 |
| 400,000,000 | 499,999,998 | 121916 | 121380 | -536 | -0.440 |
| 500,000,000 | 599,999,998 | 120696 | 120604 | -92 | -0.076 |
| 600,000,000 | 699,999,998 | 119700 | 119764 | 64 | 0.053 |
| 700,000,000 | 799,999,998 | 118860 | 118922 | 62 | 0.052 |
| 800,000,000 | 899,999,998 | 118135 | 118025 | -110 | -0.093 |
| 900,000,000 | 999,999,998 | 117499 | 117907 | 408 | 0.347 |
| 1,000,000,000 | 1,099,999,998 | 116932 | 117186 | 254 | 0.217 |
| 1,100,000,000 | 1,199,999,998 | 116422 | 116211 | -211 | -0.181 |
| 1,200,000,000 | 1,299,999,998 | 115958 | 115612 | -346 | -0.298 |
| 1,300,000,000 | 1,399,999,998 | 115534 | 115512 | -22 | -0.019 |
| 1,400,000,000 | 1,499,999,998 | 115142 | 115547 | 405 | 0.352 |
| 1,500,000,000 | 1,599,999,998 | 114779 | 114575 | -204 | -0.178 |
| 1,600,000,000 | 1,699,999,998 | 114441 | 115105 | 664 | 0.580 |
| 1,700,000,000 | 1,799,999,998 | 114124 | 113950 | -174 | -0.152 |
| 1,800,000,000 | 1,899,999,998 | 113827 | 113708 | -119 | -0.105 |
| 1,900,000,000 | 2,000,000,000 | 113547 | 113455 | -92 | -0.081 |
+---------------+---------------+--------------+--------------+------------------+--------------------+
| 2 | 2,000,000,000 | 2385773 | 2385819 | 46 | 0.002 |
+---------------+---------------+--------------+--------------+------------------+--------------------+ GFN7 Prime b Values: https://drive.google.com/open?id=1WzGsRSxrXhjUH4UkjzEgf3kMBL04V3Vu
Present status and future plans:
Known status of GFNs 1-12:
1 - Tested to b=1G with list available on Yves' site
2 - Tested to b=100M with list available on Yves' site, Possibly tested to b=1G
3 - Tested to b=10M with list available on Yves' site, Possibly tested to b=1G
4 - Tested to b=10M with list available on Yves' site, Possibly tested to b=1G
5 - Tested to b=10M with list available on Yves' site, Possibly tested to b=100M
6 - Tested to b=10M with list available on Yves' site, Possibly tested to b=100M, Tested by Kellen to b=2G, list linked above.
7 - Tested to b=9M with list available on Yves' site, Possibly tested to b=100M, Tested by Kellen to b=2G, list linked above.
8 - Tested to b=7M with list available on Yves' site, Possibly tested to b=100M
9 - Tested to b=6M with list available on Yves' site, Possibly tested to b=100M
10 - Tested to b=5M with list available on Yves' site, Possibly tested to b=100M
11 - Tested to b=4M with list available on Yves' site, Possibly tested to b=100M
12 - Tested to b=3M with list available on Yves' site, Possibly tested to b=100M
Status of Search to b=2,000,000,000:
1 - Sieved, testing underway, ETC Late March
2 - Sieved, testing underway, ETC Late March
3 - Sieved, testing underway, ETC Late March
4 - Sieved, testing underway, ETC Early March
5 - Sieved, testing underway, ETC Early March
6 - Complete (single pass)
7 - Complete (single pass)
8 - Sieved, testing underway, ETC Late March
9 - Sieving underway, ETC to optimal Mid March
10 - Sieving underway, ETC to optimal Late March
11 - Sieving underway, ETC to optimal Early April
12 - Sieving underway, ETC to optimal Late April
I plan on testing everything up to GFN10 to b=2,000,000,000, however I am not sure if GFN11 and GFN12 are within my (reasonable) capabilities. Some napkin math indicates that GFN11 will take ~35 CPU years and GFN12 will take ~150 CPU years to test. I will run some tests once the sieves are complete and see how things look then. GFN10 may also prove to be outside of my reasonable capabilities although I am fairly sure that I will get through it.
Regards,
Kellen
P.S. If anyone is interested in double-checking this data I can make all factor, candidate and residue files available.
P.P.S. Please keep in mind that this is my first foray into anything even approaching this scale. I may have made some (or many) mistakes, but will do my best to fix them if they are fixable :) | |
|
|
If you are sure your lists are absolutely correct (they do not want sporadic errors (false positives or omissions)), you could add larger b-files to A006316 and A056994. They have "Table of n, a(n) for n=1..1000" right now, in a specific simple format. That could be 1..100000 or similar. /JeppeSN | |
|
|
If you are sure your lists are absolutely correct (they do not want sporadic errors (false positives or omissions)), you could add larger b-files to A006316 and A056994. They have "Table of n, a(n) for n=1..1000" right now, in a specific simple format. That could be 1..100000 or similar. /JeppeSN
Many thanks for those links! While my confidence in the data is high, it is not absolute, as this testing was performed as a single pass for both the sieve and the primality testing. Number of primes found through all ranges previously tested by others (that I could find anyway) match with what I have tested, but there is a possibility that an error may exist past those maximum b values.
I have recorded which computers completed each test run, so perhaps in the future, once the first pass is done for the ranges I plan to test, I will re-run them on different computers to DC it. | |
|
robish Volunteer moderator Volunteer tester
 Send message
Joined: 7 Jan 12 Posts: 2213 ID: 126266 Credit: 7,531,967,424 RAC: 3,351,164
                               
|
Ill give you a hand Kellen, this sonds like fun :)
____________
My lucky number 10590941048576+1 | |
|
|
Ill give you a hand Kellen, this sonds like fun :)
Awesome, thanks Rob! Any files you want from me to do this or you just gonna go for it right from the start for a total DC of everything, sieve included? GFN6 was sieved to 250T and GFN7 was sieved to 500T. It will almost certainly take me longer to upload the factor or candidates files that it did to generate them, but if you do want them, just let me know :)
Also; fun-ness (apparently not a word) enjoyment and fun are two things that I do have 100% confidence in with this. It has been quite the adventure so far! | |
|
robish Volunteer moderator Volunteer tester
 Send message
Joined: 7 Jan 12 Posts: 2213 ID: 126266 Credit: 7,531,967,424 RAC: 3,351,164
                               
|
Ill give you a hand Kellen, this sonds like fun :)
Awesome, thanks Rob! Any files you want from me to do this or you just gonna go for it right from the start for a total DC of everything, sieve included? GFN6 was sieved to 250T and GFN7 was sieved to 500T. It will almost certainly take me longer to upload the factor or candidates files that it did to generate them, but if you do want them, just let me know :)
Also; fun-ness (apparently not a word) enjoyment and fun are two things that I do have 100% confidence in with this. It has been quite the adventure so far!
Yep total DC. I'll probably break your heart with questions mind you ;) so beee prepared ;D
____________
My lucky number 10590941048576+1 | |
|
|
Ill give you a hand Kellen, this sonds like fun :)
Awesome, thanks Rob! Any files you want from me to do this or you just gonna go for it right from the start for a total DC of everything, sieve included? GFN6 was sieved to 250T and GFN7 was sieved to 500T. It will almost certainly take me longer to upload the factor or candidates files that it did to generate them, but if you do want them, just let me know :)
Also; fun-ness (apparently not a word) enjoyment and fun are two things that I do have 100% confidence in with this. It has been quite the adventure so far!
Yep total DC. I'll probably break your heart with questions mind you ;) so beee prepared ;D
Great!! A total DC is a dream come true!
And as for your questions; bring them on! Be warned though; there is a good chance I'll return them with some of my own. This is so far beyond anything I've tackled in the past the amount of learning I had to do was pretty intense. It has been a long time since I dug myself in this hard over something.
I will give you a heads up that AthGfnSv (the 32-bit one) really really really doesn't like GFN1-4 and will probably just give up at ~147M. All of my sieving for those stops at just whatever point AthGfnSv decided it had enough. GFN5 goes to 100T, GFN6 to 250T, GFN7 to 500T, GFN8 to 2P and I am estimating that optimal for GFN9, 10, 11 and 12 are 10P, 30P, 120P and 400P, respectively (at least for my CPUs; if you have an AVX-512 capable CPU these values will likely be much lower).
Also also; you'll want an SSD for these probably. GFN1-6 have so far been limited by disc access speed and not CPU speed. GFN7 was borderline and GFN8 doesn't seem to be disc access limited if I run it on just 4 cores, but I'm certain that it would be at 5.
Hit me up with any questions you have and best of luck; hope you have as much fun as I have! | |
|
|
Oh! And one more thing! You will have to add back the low b values for GFN1-4 that get removed by sieving. Some of them are small enough that the sieve removes them even though they are valid candidates and primes ;) | |
|
streamVolunteer moderator Project administrator Volunteer developer Volunteer tester Send message
Joined: 1 Mar 14 Posts: 1033 ID: 301928 Credit: 543,624,271 RAC: 5,083
                         
|
Are you aware of a problem that AthGfnSv is buggy when b > 1G, and AthGfnSv64 is buggy at low p values? Me and Jim both had wrote own trivial programs which do initial sieving at dangerous area (low p values). Next, AthGfnSv64 could be used.
Usually we do postprocess factor files and removing candidates from the list manually. This procedure also includes check that factor really divides a candidate (it's a very simple powmod() and could be implemented even in scripted language). In this case, you don't need to double-check sieve. It's guaranteed that you'll not erroneously remove a candidate. Even if you've missed some factors - it's not a problem, just few more basic tests but nothing critical.
GFN-11,12 and probably 10 could be unbeatable with your limits. We're running GFN-13 for few years already, and running it on GPUs up to b = 400M. Considering that Genefer processing speed changes 2x-3x on each step (depending on overhead), GFN-12 is definitely a no-way for a single person, and probably should be limited to Genefer range (b < 400M).
| |
|
|
Hi Stream,
Many thanks for your summary!
Are you aware of a problem that AthGfnSv is buggy when b > 1G, and AthGfnSv64 is buggy at low p values? Me and Jim both had wrote own trivial programs which do initial sieving at dangerous area (low p values). Next, AthGfnSv64 could be used.
I became aware of issues with each, as I ran into problems with them both, but it seemed to me that the issues are related to composite candidates being left in the sieve, rather than prime candidates being removed, with the exception of the initial low-b values for GFN1-4 sieves. These were removed when sieve depth passed their value, but I added those back once the sieve stopped, ~12200 for GFN1, 110 for GFN2, 10 for GFN3 and 2 for GFN4, although I just added sequentially all even b values up to the first one left in the candidates file. AthGfnSv64 will not work for GFN1-4 either, so the sieve for those stops extremely low, at about 147M. If I end up testing a bunch more candidates because of this I am OK with that. It would be really bad if valid primes were erroneously removed though...
Usually we do postprocess factor files and removing candidates from the list manually. This procedure also includes check that factor really divides a candidate (it's a very simple powmod() and could be implemented even in scripted language). In this case, you don't need to double-check sieve. It's guaranteed that you'll not erroneously remove a candidate. Even if you've missed some factors - it's not a problem, just few more basic tests but nothing critical.
This is also something that I did not do. For the most part, this stuff is well beyond my capabilities so I relied only on the factor checking built into AthGfnSv. If you or Jim or anyone else with the skills, tools and knowledge would be willing to help out with this and either verify that the candidates files that I've generated are valid, or generate valid candidates files I would be infinitely appreciative of the help, even if it means starting testing from scratch on GFN1-4! For all of the other sieves I used AthGfnSv to about 120M and stopped it before 147M which is where I noted that it has issues with the lower GFNs, then switched to AthGfn64.
For GFN5-8 (and soon, 9 and 10), it is likely easier to construct a candidates file from the sieve files. I can easily get these factor files to anyone confident in constructing a candidates file from it, although I would much prefer that that file is used to ensure that the candidates files I have already used were valid, as this testing is largely complete.
GFN-11,12 and probably 10 could be unbeatable with your limits. We're running GFN-13 for few years already, and running it on GPUs up to b = 400M. Considering that Genefer processing speed changes 2x-3x on each step (depending on overhead), GFN-12 is definitely a no-way for a single person, and probably should be limited to Genefer range (b < 400M).
Totally agreed about 11 and 12 for this one and I will probably limit it to b<400M (assuming I figure out how to feed a candidate file into Genefer, which I haven't figured out yet :) ). I ran some tests yesterday at a variety of b-ranges on GFN 10 and I'd agree as well that it is not a feasible GFN to test to 2G with a small number of computers, although I may still try. Ultimately I just like the idea of having everything finished and done so that there are no gaps in testing and no higher GFN n values have been continuously tested to a higher b value than any lower n. Getting 1-9 to 2G and then 10+ to 400M (over time) would make it all very neat and tidy :)
Now that it has been mentioned and I've looked into it, I would like to get these lists verified well enough to post to OEIS so I started looking into what would be required to validate results (comparing residues) if someone does DC all of my testing. I am 100% confident that reliably comparing residues is above my competency by any means other than hand-checking (which is not particularly practical with 109 candidates), so if you, or anyone else, is able to help with that too it would be very much appreciated.
Even if no one wants to help with this stuff (and I don't blame you or anyone else if you don't want to; this is an enormous undertaking, much, much bigger than I originally thought), it is still my intention to move forward with this and complete up to GFN9, b=2G, even if my methodology is somewhat flawed. At the very least we will generate a list of b values that is probably right, and a huge number of residue files that can be used in the future when someone more competent than myself decides to do a search of these ranges. I am somewhat bolstered by the fact that I have so far not missed a prime nor found one that was not previously found in Yves' testing, so I can't have completely screwed up! :) | |
|
|
I was just having a bit of a think about this and GFN1 has a property that none of the other GFNs have that makes sieving almost unnecessary. Every b value ending in '2' or '8' for GFN1 will result in a multiple of 5, so they can just be discarded with no further work (well, except for b=2). If this is true then 400 million candidates can be easily eliminated without any formal sieving effort.
Are there any other similar and very easy/straightforward rules that can be applied to filter out candidates for the low n value sieves? I can generate a file containing all candidates and then apply simple rules to delete them, but it has to be as simple as "ending in 8" or "ending in 26".
Me and Jim both had wrote own trivial programs which do initial sieving at dangerous area (low p values). Next, AthGfnSv64 could be used.
During this think I also realized that sieving to 2G for GFN1 would eliminate the need for testing altogether as long as there was a mechanism in place to prevent removal of a candidate which equals the p value being sieved. Do the sieve programs you mentioned prevent removal of candidates which are exactly equal to the p value? For example; with AthGfnSv, when p=2917, it removed 54 from the GFN1 candidates list because 542+1=2917. If it is possible for the software to know not to do this then the list of GFN1 primes would be trivial to generate.
P.S. I never noticed until thinking about this, but this train of thought has led me to realize that all GFN primes end in either 7 (~80%) or 1 (~20%). This has blown my non-mathematician mind. | |
|
|
b values ending in 1, 3, 5, 7, and 9 will result in a multiple of 2, so they can just be discarded with no further work (well, except for b=1).
This rule with 2 (odd/even) works for all n (all GFNn).
Your rule with 5 is not relevant for higher n. Modulo 5, a fourth power is congruent to either 1 (invertible) or 0. So adding one, the expression b^4+1 will be either 2 or 1 modulo 5, so never divisible by 5.
Another way of seeing it is that for n≥2 the divisors must have the form k*2^{2+1} + 1, or 8k+1. And 5 does not have the form 8k+1.
/JeppeSN | |
|
|
b values ending in 1, 3, 5, 7, and 9 will result in a multiple of 2, so they can just be discarded with no further work (well, except for b=1).
This rule with 2 (odd/even) works for all n (all GFNn).
Your rule with 5 is not relevant for higher n. Modulo 5, a fourth power is congruent to either 1 (invertible) or 0. So adding one, the expression b^4+1 will be either 2 or 1 modulo 5, so never divisible by 5.
Another way of seeing it is that for n≥2 the divisors must have the form k*2^{2+1} + 1, or 8k+1. And 5 does not have the form 8k+1.
/JeppeSN
Perfect, thanks! I was hoping for more simple rules for elimination based on b-value alone, but it looks like there really are just those ones. I'll still take it though as that's a big chunk of candidates eliminated easily and without risk of software error :) | |
|
Yves Gallot Volunteer developer Project scientist Send message
Joined: 19 Aug 12 Posts: 820 ID: 164101 Credit: 305,989,513 RAC: 1,728

|
Hi Kellen,
don't sieve small n, a simple Pari-gp program is able to generate small GFN primes more quickly than a sieve:
cnt = 0;
forstep (b = 2, 2000000000, 2,
p = b^2+1;
c = Mod(2, p)^(p-1);
if (c == 1, if (isprime(p), cnt++; print(cnt, " ", b)));
);
Yves | |
|
|
Hi Kellen,
don't sieve small n, a simple Pari-gp program is able to generate small GFN primes more quickly than a sieve:
cnt = 0;
forstep (b = 2, 2000000000, 2,
p = b^2+1;
c = Mod(2, p)^(p-1);
if (c == 1, if (isprime(p), cnt++; print(cnt, " ", b)));
);
Yves
Hi Yves,
Thank you very much for this code. I will look into Pari-gp and give this a go and will run it for GFN1 then GFN2 and higher until it stops running in a reasonable time.
Regards,
Kellen | |
|
|
Hi Kellen,
don't sieve small n, a simple Pari-gp program is able to generate small GFN primes more quickly than a sieve:
cnt = 0;
forstep (b = 2, 2000000000, 2,
p = b^2+1;
c = Mod(2, p)^(p-1);
if (c == 1, if (isprime(p), cnt++; print(cnt, " ", b)));
);
Yves
Hi Yves,
Many thanks for this!! It is extraordinarily efficient and has given us a viable validation technique that is within my capabilities for execution :)
I have generated primes for 2≤b≤2,000,000 for GFN1, GFN2, GFN4, GFN6 and GFN7, and for 1,999,800,000≤b≤2,000,000,000 for GFN6 and GFN7 with your program and compared the output with the findings from LLR testing and they are identical. This Pari-gp program is significantly faster than LLR testing for everything up to GFN6 (despite the fact that GFN6 was sieved to 250T) and only about 50% longer than GFN7 (which has very few candidates compared to the others).
I am testing GFN8 at the moment and will compare speed between your program and LLR. What we will likely end up doing is testing everything with LLR and comparing it with the output from your program (or multiple passes of either LLR or your program) to make sure they match. If the output matches then an error or omission is pretty unlikely given the completely different testing methodologies.
To the best of your knowledge, are there any limits with Pari-gp that would lead to invalid results with higher GFN n or b values? If not, I will probably set it to run on one of my non-networked computers for GFN9 and just let it do its thing for as long as it takes to finish so that we can validate those LLR findings as soon as they are done.
Thank you,
Kellen | |
|
|
PARI/GP will never give wrong result, even with high n and b values. But it will be slow. You can use ispseudoprime instead of isprime, and that will be faster at verifying the PRPs. But with a theoretical probability that it will report a composite number as "prime". But that would be a sensation. No examples are known.
You can use ispseudoprime alone: cnt = 0; forstep(b = 2, 2000, 2, if(ispseudoprime(b^128+1), cnt++; print(cnt, " ", b)))
Of course that is silly when we know p has a form where we can do a fast deterministic test.
You can also use the 2-PRP test alone and leave it to genefer or another program to verify the candidates: cnt = 0; forstep(b = 2, 2000, 2, p = b^128+1; c = Mod(2, p)^(p-1); if(c == 1, cnt++; print(cnt, " ", b)))
You can change to 3-PRP (c = Mod(3, p)^(p-1)) if you are annoyed by the composite Fermat numbers appearing in the output.
/JeppeSN | |
|
Yves Gallot Volunteer developer Project scientist Send message
Joined: 19 Aug 12 Posts: 820 ID: 164101 Credit: 305,989,513 RAC: 1,728

|
2p-1 ?= 1 (mod p) is a fast and strong test.
JeppeSN asked "If b is even and not a power of two, can b4 + 1 be a pseudoprime?" and the question is still open.
Then for n >= 8, the faster approach is likely to sieve all candidates, remove composites with 2p-1 ?= 1 (mod p) and finally prove primality of probable primes.
The main problem is how to check probable-primality efficiently with "medium-sized" numbers? It is not easy because llr or genefer are optimized for very large numbers and the algorithms of GNU GMP (and then Pari) are beginning to be inefficient.
I shall look into the code of genefer and write a version dedicated to "small" n. It must be able to test several candidates at the same time and bmax can easily be extended to 231. | |
|
streamVolunteer moderator Project administrator Volunteer developer Volunteer tester Send message
Joined: 1 Mar 14 Posts: 1033 ID: 301928 Credit: 543,624,271 RAC: 5,083
                         
|
Do the sieve programs you mentioned prevent removal of candidates which are exactly equal to the p value? For example; with AthGfnSv, when p=2917, it removed 54 from the GFN1 candidates list because 542+1=2917. If it is possible for the software to know not to do this then the list of GFN1 primes would be trivial to generate.
Good catch! I think none of our programs are checking for this situation. They generate a list of possible factors and do the test. Such match seems to be unlikely on high N, but I'd better check it.
GFN-N factor always have a form of x*2N+1+1 (x = any number, but result must be prime). In case of N=1, both formulas are simplified to:
GFN-1: b21+1 = b2+1
Factor: x*21+1+1 = x*4+1
This leads to equation
b2 = x*4
Which will have solution if 'x' is a square, like in your example.
EDIT: this problem exists from GFN-1 to GFN-5 only. Even in GFN-6, first candidate to test is 2^64+1, which is about 18446P - much higher then any reasonable factor (sieving limit) for GFN-6. On GFN-7 and above, even first candidate (2^128+1) = 3,4e38. It exceeds any possible factor by many orders, making this situation (candidate is equal to factor) impossible. | |
|
|
Of course, to test 54^2 + 1, you sieve with primes of the form p = 4*x + 1, as said already, and you can stop at the square root of the candidate, i.e. at 54 in this case. So you would check p = 5, 13, 17, 29, 37, 41, 53, and if none of them divides 54^2 + 1, then 54^2 + 1 is a prime (primality test by exhaustive trial division).
So I do not know if you can write the sieve program such that it starts sieving candidates for divisibility by p, only from candidates exceeding p^2.
Of course, you could also just insert an extra check just before the divisor is output to check if that divisor is proper or improper (equal to the candidate).
(For comparison, with a candidate 54^1024 + 1, the prime form is p = 2048*x + 1, so you check p = 12289, 18433, 40961, 59393, 61441, . . ., but you would have to check to 54^512 or 10^887 to be "finished", and of course it is not practically possible.)
/JeppeSN | |
|
|
Thanks for your comments everyone!
You can use ispseudoprime alone: cnt = 0; forstep(b = 2, 2000, 2, if(ispseudoprime(b^128+1), cnt++; print(cnt, " ", b)))
I have tried the PRP test in Pari-gp and compared speed with the original one posted and they are comparable for GFN6, although it is possible that a difference in speed would be more pronounced at a higher n value, so I will test with GFN8 later.
I have also made a file with the GFN generation program nested inside the PRP program, or at least I think I have... If you see any errors in what is below please let me know. The hope is that it will be faster due to the "sieving" of the PRP, but still only output b values definitively resulting in a prime, thereby eliminating the need to run the PRP output through secondary verification.
cnt = 0; forstep(b = 1750000, 2000000, 2, if(ispseudoprime(b^64+1), p = b^64+1; c = Mod(2, p)^(p-1); if (c == 1, if (isprime(p), cnt++; write("GFN6PseudoPO.txt", b)));));
I am not at all familiar with this programming language (or any programming language :) ), so it may be a bit messy at the end. Not 100% sure where the closing brackets and semi-colons fit into the whole thing, but this does seem to work.
I shall look into the code of genefer and write a version dedicated to "small" n. It must be able to test several candidates at the same time and bmax can easily be extended to 231.
This would be amazing! The "several candidates at the same time" part especially so. Do you think it is possible to get 100% core utilization with smaller GFNs if many are run in parallel? As it stands, there is some limit that prevents 100% core utilization even when running multiple tasks, so even my GT1030s run comparably fast to my GTX 1080ti for GFN-13. If it is possible to process a large number of candidates in parallel, it would make testing of the smaller GFNs extremely fast!
this problem exists from GFN-1 to GFN-5 only. Even in GFN-6, first candidate to test is 2^64+1, which is about 18446P - much higher then any reasonable factor (sieving limit) for GFN-6. On GFN-7 and above, even first candidate (2^128+1) = 3,4e38. It exceeds any possible factor by many orders, making this situation (candidate is equal to factor) impossible.
Thank you for looking into this! It was definitely not a problem for the bigger sieves, and I did not even have an issue with GFN5 as it was only sieved to 100T. My curiousity came from wondering about the possibility of quickly generating all GFN1 prime b values by sieving to 2G, then testing to b = sqrt(2*109) with another program (although just generating that list with Pari-gp is incredibly fast). If the sieve program did not remove b values which were exactly equal to the prime value being sieved then the secondary testing to ~44720 would not even be necessary.
Thinking about this though, GFN2 is outside of the reasonable limits for doing this though as we would have to sieve to ~4,000P, which would take much much longer than just testing it all. | |
|
Yves Gallot Volunteer developer Project scientist Send message
Joined: 19 Aug 12 Posts: 820 ID: 164101 Credit: 305,989,513 RAC: 1,728

|
cnt = 0; forstep(b = 1750000, 2000000, 2, if(ispseudoprime(b^64+1), p = b^64+1; c = Mod(2, p)^(p-1); if (c == 1, if (isprime(p), cnt++; write("GFN6PseudoPO.txt", b)));));
I am not at all familiar with this programming language (or any programming language :) ), so it may be a bit messy at the end. Not 100% sure where the closing brackets and semi-colons fit into the whole thing, but this does seem to work.
It's correct. Note that output is not some pseudo-primes but some primes because of the if (isprime(p) test.
Do you think it is possible to get 100% core utilization with smaller GFNs if many are run in parallel? As it stands, there is some limit that prevents 100% core utilization even when running multiple tasks, so even my GT1030s run comparably fast to my GTX 1080ti for GFN-13. If it is possible to process a large number of candidates in parallel, it would make testing of the smaller GFNs extremely fast!
The GTX 1080 Ti is a 3584-core GPU. On Pascal, the latency of an instruction is 6 cycles. Then we must be able to execute 6*3584 = 21504 independent instructions at the same time. The implementation of genefer uses a base b representation of numbers: the size of b1024+1 is 1024 words, it is not sufficient to get 100% core utilization. Yes, the idea is to test 16 or 32 numbers concurrently. | |
|
|
It's correct. Note that output is not some pseudo-primes but some primes because of the if (isprime(p) test.
Perfect; thank you for confirming this. The file name has Pseudo in it just because I had modified it quickly from the code JeppeSN posted after putting your code in. I have now renamed it to something clearer. Testing to see if it is significantly faster than without the PRP test now.
The GTX 1080 Ti is a 3584-core GPU. On Pascal, the latency of an instruction is 6 cycles. Then we must be able to execute 6*3584 = 21504 independent instructions at the same time. The implementation of genefer uses a base b representation of numbers: the size of b1024+1 is 1024 words, it is not sufficient to get 100% core utilization.
Interesting, and good to know! With this information I would guess that I should be able to get 100% utilization with GFN-15 tests as those are b32768, but that doesn't seem to be the case either; instead I get approximately 70%, so I think there is some other limit impacting this as well. GFN-16 is very close to 100% though and everything past that is 99%+. Of course it is also possible that HardwareInfo64 is just incorrectly reporting the utilization and it actually is 100%; which would not surprise me much.
Yes, the idea is to test 16 or 32 numbers concurrently.
This would be a really impressive improvement for the smaller GFNs and, correct me if I am wrong, would also significantly improve the throughput of the work done on Stream's server with both GFN-13 and GFN-14. GFN-13 will likely be finished to b=400M within the next few months, but GFN-14 has a lot of life left in it. Very exciting work! | |
|
|
Me and Jim both had wrote own trivial programs which do initial sieving at dangerous area (low p values). Next, AthGfnSv64 could be used.
As the first step in an effort to make sure that the sieves that I generated are valid and only composite candidates were removed I also wrote something that generates factor files for low p values and have run it over several ranges without any errors (that I found anyway). Before I go much further with this, if someone doesn't mind taking a quick look to makes sure there are no errors I would be grateful. It should output in the same format as AthGfnSv except without the "^256+1" These factor files are immense and I am trying to pare down the size where possible.
The file below should be sieving the b range from 2-100M up to p=~1,000,000 for GFN8 and outputting the factors and b values to a text file. It seems to be doing this just fine, but if anyone notices anything strange about it, please let me know.
forstep (x = 1, 1954, 1, y=x*512+1; if (isprime(y), forstep (b = 2, 100000000, 2, p=b^256+1; c=(Mod(p,y)); if(c==0, write("GFN8Factors0-100M_1M.txt", y," | ",b)))));
Usually we do postprocess factor files and removing candidates from the list manually. This procedure also includes check that factor really divides a candidate (it's a very simple powmod() and could be implemented even in scripted language). In this case, you don't need to double-check sieve. It's guaranteed that you'll not erroneously remove a candidate. Even if you've missed some factors - it's not a problem, just few more basic tests but nothing critical.
I will work on factor validation and candidate file generation next and see if it is something I can pull off. I've stretched my brain pretty far on this already, but a little more stretching can't hurt (although if someone else wanted to do this for GFN8-12 based on factor files that I have generated and will generate, I wouldn't argue...*not-so-subtle plea for help*).
Also, there is a relatively high degree of confidence that we have figured out how to compare residues so we should be able to validate the results now too. The method is somewhat time consuming, but seems reliable (tested by introducing random errors and untested values into residues of ~5 million tests and seeing if they were found).
And finally, as an aside for those who don't understand this stuff (like me), making this sieve has taught me many interesting things that I would never have understood if not for getting hands-on with it. While this will be obvious to anyone who has studied this, it may be interesting to others and I found it very enlightening. This is my favorite realization so far:
Sieving at high n values progresses in P/day faster than low n values because far fewer prime factors are possible. Yves and JeppeSN both mentioned this and Stream summed up the concept below by saying that "GFN-N factor always have a form of x*2N+1+1", but I didn't really understand the significance without seeing the effect. This means that as N increases by 1 there are roughly half as many possible factors in any given range. As an example, I have made a table of the total number of possible factors between 2 and 1,000,000 for each GFN from 1 to 8:
1 - 39175
2 - 19552
3 - 9761
4 - 4912
5 - 2456
6 - 1223
7 - 605
8 - 298 I had always wondered why the higher GFNs sieved so much quicker and used so much less CPU than the lower GFNs and now I know :) | |
|
|
The file below should be sieving the b range from 2-100M up to p=~1,000,000 for GFN8 and outputting the factors and b values to a text file. It seems to be doing this just fine, but if anyone notices anything strange about it, please let me know.
forstep (x = 1, 1954, 1, y=x*512+1; if (isprime(y), forstep (b = 2, 100000000, 2, p=b^256+1; c=(Mod(p,y)); if(c==0, write("GFN8Factors0-100M_1M.txt", y," | ",b)))));
This may be a bit better:
forstep (y=512+1, +oo, 512, if (isprime(y), forstep (b = 2, 100000000, 2, c=Mod(b,y)^256+1; if(c==0, write("GFN8Factors0-100M_1M.txt", y," | ",b)))))
In your version, b^256 is calculated as a full integer at first. It can have over a thousand figures. When you do Mod(p,y)^256 instead, it may be faster. (Not sure how much it matters.)
For example: Compare the output of 99999998^256 and Mod(99999998,16673)^256.
/JeppeSN | |
|
|
The file below should be sieving the b range from 2-100M up to p=~1,000,000 for GFN8 and outputting the factors and b values to a text file. It seems to be doing this just fine, but if anyone notices anything strange about it, please let me know.
forstep (x = 1, 1954, 1, y=x*512+1; if (isprime(y), forstep (b = 2, 100000000, 2, p=b^256+1; c=(Mod(p,y)); if(c==0, write("GFN8Factors0-100M_1M.txt", y," | ",b)))));
This may be a bit better:
forstep (y=512+1, +oo, 512, if (isprime(y), forstep (b = 2, 100000000, 2, c=Mod(b,y)^256+1; if(c==0, write("GFN8Factors0-100M_1M.txt", y," | ",b)))))
In your version, b^256 is calculated as a full integer at first. It can have over a thousand figures. When you do Mod(p,y)^256 instead, it may be faster. (Not sure how much it matters.)
For example: Compare the output of 99999998^256 and Mod(99999998,16673)^256.
/JeppeSN
Many thanks for this! I will give them both a try and compare. Anything that speeds it up will be very useful and is much appreciated.
Regards,
Kellen | |
|
|
As already said by stream, there is no need to double-check the sieve, as long as you check each factor found. If the line looks like 959815134871698800641 | 709500654^2097152+1 in the out file from the sieve (example taken from other thread), then maybe you can use some script (PARI/GP is not good with string manipulation) or regular expression to produce a file where it is written asMod(709500654, 959815134871698800641)^2097152+1 == 0 This will be extremely fast to evaluate for PARI. You can use: filedescr=fileopen("yourFileName"); while(1, line=filereadstr(filedescr); line==0 && break(); !eval(line) && error("Problem with: ",line); print1(".")); fileclose(filedescr) \\JeppeSN | |
|
|
As already said by stream, there is no need to double-check the sieve, as long as you check each factor found. If the line looks like959815134871698800641 | 709500654^2097152+1 in the out file from the sieve (example taken from other thread), then maybe you can use some script (PARI/GP is not good with string manipulation) or regular expression to produce a file where it is written asMod(709500654, 959815134871698800641)^2097152+1 == 0 This will be extremely fast to evaluate for PARI. You can use: filedescr=fileopen("yourFileName"); while(1, line=filereadstr(filedescr); line==0 && break(); !eval(line) && error("Problem with: ",line); print1(".")); fileclose(filedescr) \\JeppeSN
Thank you again for this advice; much appreciated!
I tested your factor generation code from above as well and it is very much faster, especially at high b and p values and everything is identical to the previously generated files. I don't understand how Mod(b,y)^256+1 = 0 when y is a factor of b^256+1, but it seems to work and is very fast. (In my head it should be Mod((Mod(b,y)^256+1),y) = 0, but this just means I have more to learn :) )
I also started working on something similar to what you suggest here after looking up what would be better to handle these large files line by line. The math is easily performed by PARI/GP, but after a search it seems that either Python or Perl are probably better for the file handling. I took a look at some example coding used in both and Python seems to make the most sense to me so I'll give it a go with that this weekend.
Double-checking the factors is the last thing that we can't yet do and repeating the low p sieving effort should really tidy things up. There are a lot of candidates that AthGfnSv did not remove that should have been removed at these low p values. Once that is complete then the confidence in the generated lists increases to 100%.
Thanks again!
Kellen | |
|
Yves Gallot Volunteer developer Project scientist Send message
Joined: 19 Aug 12 Posts: 820 ID: 164101 Credit: 305,989,513 RAC: 1,728

|
I don't understand how Mod(b,y)^256+1 = 0 when y is a factor of b^256+1, but it seems to work and is very fast. (In my head it should be Mod((Mod(b,y)^256+1),y) = 0, but this just means I have more to learn :) )
Mod(a, b) not only creates 'a modulo b' but defines the congruence class of a modulo b.
This is not a % b but a such that a in Z/bZ.
Then Mod(b, y)^256 + 1 is still a residue modulo y and you don't have to reduce it again. | |
|
rogueVolunteer developer
 Send message
Joined: 8 Sep 07 Posts: 1256 ID: 12001 Credit: 18,565,548 RAC: 0
 
|
As already said by stream, there is no need to double-check the sieve, as long as you check each factor found. If the line looks like959815134871698800641 | 709500654^2097152+1 in the out file from the sieve (example taken from other thread), then maybe you can use some script (PARI/GP is not good with string manipulation) or regular expression to produce a file where it is written asMod(709500654, 959815134871698800641)^2097152+1 == 0 This will be extremely fast to evaluate for PARI. You can use: filedescr=fileopen("yourFileName"); while(1, line=filereadstr(filedescr); line==0 && break(); !eval(line) && error("Problem with: ",line); print1(".")); fileclose(filedescr) \\JeppeSN
You can run these factors thru pfgw where each line is a row like this:
959815134871698800641 | 709500654^2097152+1
If you have grep it would be something like this: pfgw64 factors.txt | grep -v Zero > invalid.txt
I use this to verify the factors found by my sieving programs. | |
|
|
I don't understand how Mod(b,y)^256+1 = 0 when y is a factor of b^256+1, but it seems to work and is very fast.
Yves's explanation is correct! If you are pedantic, it is reallyMod(b,y)^256+Mod(1,y) === Mod(0,y) and everything is calculated in the ring Z/yZ. /JeppeSN | |
|
|
You can run these factors thru pfgw where each line is a row like this:
959815134871698800641 | 709500654^2097152+1
That is smarter than trying to transform the file into something PARI/GP understands (like I suggested). /JeppeSN
| |
|
|
I don't understand how Mod(b,y)^256+1 = 0 when y is a factor of b^256+1, but it seems to work and is very fast.
Mod(a, b) not only creates 'a modulo b' but defines the congruence class of a modulo b.
This is not a % b but a such that a in Z/bZ.
Then Mod(b, y)^256 + 1 is still a residue modulo y and you don't have to reduce it again.
Yves's explanation is correct! If you are pedantic, it is reallyMod(b,y)^256+Mod(1,y) === Mod(0,y) and everything is calculated in the ring Z/yZ. /JeppeSN
Good to know, thanks! I made the (incorrect) assumption that the mod function would return the remainder only for a single step, and not do anything else. This factor generation script is now working beautifully and is efficient enough to do some very low p sieving. I also put a print function in it so that it displays the p value it is working with, so now it looks like this:
forstep (y=64+1, 1000000, 64, if (isprime(y), print(y); forstep (b = 2, 2000000000, 2, c=Mod(b,y)^32+1; if(c==0, write("GFN5Factors_2-1M.txt", y," | ",b)))))
I am very pleased with this and will move forward with it. The reliability is 100% from what I've seen and the speed is excellent for this purpose.
You can run these factors thru pfgw where each line is a row like this:
959815134871698800641 | 709500654^2097152+1
If you have grep it would be something like this: pfgw64 factors.txt | grep -v Zero > invalid.txt
I use this to verify the factors found by my sieving programs.
Thank you for this tip! I looked up "grep" and it appears to be only for Linux, which I am a total newbie with, so I gave Python a go (which I am also a total newbie with, but it made a little more sense to me) and have made something that works reasonably well. It is probably inefficient somewhere, but it did verify a file of 25,000,000 factors in 4 minutes for GFN8 and properly identified and recorded the 7 errors I introduced. Here is the code if anyone is interested (either in using it or having a laugh at whatever inefficiencies I wrote ;P ):
with open ("GFN8Factors0-100M_1M-2.txt") as f:
for t in f:
p, b = t.split()
p, b = [int(p), int(b)]
c = ((b % p)**256+1) % p
if c!=0:
f = open("GFN8FactorErrors.txt", "a")
p = str(p)
b = str(b)
f.write(p)
f.write(" ")
f.write(b)
f.write("\n")
f.close()
f = open("GFN8Factors0-100M_1M-2.txt")
And with that I think that using the combination of the factor file generating code for PARI/GP for the low p values, AthGfn64 B306 for higher p values, the Python script above for factor verification and EmEditor for candidate file generation, we are now good to generate 100% reliable candidate files. EmEditor is also the program that we can use for residue validation as it allows for easy manipulation of the results files and extraction of the residues, so the results can now be verified through two runs on two different PCs.
Thank you very much to everyone who has helped with this. You have helped turn this from some geologist faffing about with things he doesn't understand into some geologist working slowly but confidently towards a reliable result for things that he is learning lots about and is having a ton of fun with :) | |
|
|
with open ("GFN8Factors0-100M_1M-2.txt") as f:
for t in f:
p, b = t.split()
p, b = [int(p), int(b)]
c = ((b % p)**256+1) % p
if c!=0:
f = open("GFN8FactorErrors.txt", "a")
p = str(p)
b = str(b)
f.write(p)
f.write(" ")
f.write(b)
f.write("\n")
f.close()
f = open("GFN8Factors0-100M_1M-2.txt")
This is what I get when I run the script:
Traceback (most recent call last):
File "xxxx", line 3, in <module>
p, b = t.split()
ValueError: too many values to unpack (expected 2)
Did I do something wrong?
____________
My lucky number is 6219*2^3374198+1
| |
|
|
This is what I get when I run the script: ...
Check how the split command splits a given line. I would assume it works by splitting the string by spaces, so in order for the python program that Kellen wrote to work you probably need input files of the format:
prime base
instead of
prime | base^256+1
This would explain that it receives more values (in this case three, one substring is just "|") than it expects (two).
| |
|
|
This is what I get when I run the script: ...
Check how the split command splits a given line. I would assume it works by splitting the string by spaces, so in order for the python program that Kellen wrote to work you probably need input files of the format:
prime base
instead of
prime | base^256+1
This would explain that it receives more values (in this case three, one substring is just "|") than it expects (two).
You got it Matzetoni! I removed the " | " and the "^256+1" from all of the files to make them smaller and easier to handle. Each GFN has a minimum of 25GB of factor files, so anything I can do to pare them down for factor verification makes things easier :) | |
|
|
ahhh thanks!!
____________
My lucky number is 6219*2^3374198+1
| |
|
streamVolunteer moderator Project administrator Volunteer developer Volunteer tester Send message
Joined: 1 Mar 14 Posts: 1033 ID: 301928 Credit: 543,624,271 RAC: 5,083
                         
|
I've recreated sieve for GFN-6. It's currently sieved to 54T (0,054P) and contain 140M candidates. I'll try to squeeze more out it with AthGfn64. When it'll be ready, it could be used by a person who wish to double-check Kellen's work. Next I can write scripts to merge and compare results from both crunchers. And we'll have fully double-checked results.
As you can see, my sieving took a while because I had to sieve "dangerous area" where AthGfn64 is buggy (p < b) with own, simple and very slow program. Even being GPU-assisted, it took few days to process. But I found a way to improve it's speed a bit introducing special "AthGfn64 fix" sieve mode (in this mode, no need to test small candidates b < p, they're already removed by AthGfn64). So next sieves will be done faster.
| |
|
|
I've recreated sieve for GFN-6. It's currently sieved to 54T (0,054P) and contain 140M candidates. I'll try to squeeze more out it with AthGfn64. When it'll be ready, it could be used by a person who wish to double-check Kellen's work. Next I can write scripts to merge and compare results from both crunchers. And we'll have fully double-checked results.
As you can see, my sieving took a while because I had to sieve "dangerous area" where AthGfn64 is buggy (p < b) with own, simple and very slow program. Even being GPU-assisted, it took few days to process. But I found a way to improve it's speed a bit introducing special "AthGfn64 fix" sieve mode (in this mode, no need to test small candidates b < p, they're already removed by AthGfn64). So next sieves will be done faster.
That's awesome!! Many thanks Stream!!
I have validated the sieves to the best of my ability and am testing GFN6 for a second pass and GFN7 is being done by Rob, but we have been trying to figure out the details of residue validation and file handling, plus it sounds like you have managed to remove a lot more candidates than me ;)
If I can get you the results files for both GFN6 runs and Rob and I can get the results files for the GFN7 runs to you, would you be able to validate them and make sure that all candidates were tested, or would you prefer that we try to do it with your script?
Also; if you are planning on doing the higher GFN candidates files as well I have a massive amount of AthGfn64 factors files that I can get loaded onto Google Drive to help things along.
Your efforts with this are immeasurably appreciated, so anything you need/want just let me/us know! | |
|
|
Just got home and checked my GFN6 Candidates file and yeah; yours is way better :) Mine has 147,722,870 Candidates, so there were a lot left in that definitely should have been removed.
I should also mention that I am nearly finished a first pass of GFN8 and have started the verification pass on a second computer. Because GFN8 is a much longer set, I will finish the first pass and the 400M worth of verification pass that I have running and then stop until the better sieve is finished. That will save quite a bit of time even if a just a handful of candidates are removed. Everything up to GFN8 was already in progress by the time I gained the ability to generate the small factors and remove them, so I just left it all going.
Is your validation script able to look only at the residues for b values which appear in your candidates file? When comparing to my results files it will have to skip a lot of lines compared to the results files from yours.
I will PM you with a download link for the AthGfn64 Factor files for GFN8 to 2P. GFN9 will be at 10P mid-next-week, so I'll provide all those too (and GFN10 to 30P, 11 to 100P and 12 to 400P as those complete, or farther, if you want). | |
|
streamVolunteer moderator Project administrator Volunteer developer Volunteer tester Send message
Joined: 1 Mar 14 Posts: 1033 ID: 301928 Credit: 543,624,271 RAC: 5,083
                         
|
I've joined similar quotes from both your posts in reply.
I have validated the sieves to the best of my ability and am testing GFN6 for a second pass and GFN7 is being done by Rob, but we have been trying to figure out the details of residue validation and file handling, plus it sounds like you have managed to remove a lot more candidates than me ;)
Just got home and checked my GFN6 Candidates file and yeah; yours is way better :) Mine has 147,722,870 Candidates, so there were a lot left in that definitely should have been removed.
Yes, I've removed more because AthGfn64 loses many small factors p < b (i.e. below 2,000,000), and these small factors will cancel lot of candidates.
Also I've applied factors from your high sieve you've sent me (up to 250T / 0,25P) and final sieve size is 133,541,769 candidates now.
If I can get you the results files for both GFN6 runs and Rob and I can get the results files for the GFN7 runs to you, would you be able to validate them and make sure that all candidates were tested, or would you prefer that we try to do it with your script?
Is your validation script able to look only at the residues for b values which appear in your candidates file? When comparing to my results files it will have to skip a lot of lines compared to the results files from yours.
I think you both should post your files (residues) somewhere (like Google Drive), I'll write a script to merge and compare them using my sieve files. I'll post final results somewhere too.
The script is not ready yet but it'll be a quite trivial Perl or PHP program. It should read a candidate from sieve, find corresponding residues in files presented by two crunchers (both residues must exist), and compare them. This sounds simple but may need some tricks and optimization because all these files are huge and straightforward approach may not work. It's not a problem for me. And yes, some results will be unused because my sieve is smaller then yours, but it also is not a problem.
And of course you could write this thing yourself as a programming exercise :)
Also; if you are planning on doing the higher GFN candidates files as well I have a massive amount of AthGfn64 factors files that I can get loaded onto Google Drive to help things along.
Factors above 30-50 T will help. Everything below is unnecessary; it takes too much space and I could sieve up to 50T within one day using AthGfn64.
I should also mention that I am nearly finished a first pass of GFN8 and have started the verification pass on a second computer. Because GFN8 is a much longer set, I will finish the first pass and the 400M worth of verification pass that I have running and then stop until the better sieve is finished.
OK, I've started making optimal GFN-8 sieve right now, so you'll have less work to do.
| |
|
|
Yes, I've removed more because AthGfn64 loses many small factors p < b (i.e. below 2,000,000), and these small factors will cancel lot of candidates.
Also I've applied factors from your high sieve you've sent me (up to 250T / 0,25P) and final sieve size is 133,541,769 candidates now.
Factors above 30-50 T will help. Everything below is unnecessary; it takes too much space and I could sieve up to 50T within one day using AthGfn64.
I am glad to hear that the factor files were useful. For the sieving efforts I sieved ranges from p=~147M-100G, then p=100G-10T, then p=10T+ in one or more separate files. I will not send the 147M-10T files, and will remove everything less than 30T from the remaining files and send them for each GFN as soon as they are ready.
I think you both should post your files (residues) somewhere (like Google Drive), I'll write a script to merge and compare them using my sieve files. I'll post final results somewhere too.
The script is not ready yet but it'll be a quite trivial Perl or PHP program. It should read a candidate from sieve, find corresponding residues in files presented by two crunchers (both residues must exist), and compare them. This sounds simple but may need some tricks and optimization because all these files are huge and straightforward approach may not work. It's not a problem for me. And yes, some results will be unused because my sieve is smaller then yours, but it also is not a problem.
I will get the first pass of GFN6 and GFN7 uploaded this weekend and the second pass of GFN6 probably the weekend after. Rob is making good progress on GFN7 and also has Google Drive, so we can definitely make this work :)
And of course you could write this thing yourself as a programming exercise :)
Agreed!! I have been enjoying this part of it a lot and will certainly give it my best effort to see if I can come up with something efficient enough to use. The results files for 100M test ranges are about 0.5-1GB, and I am finding that when Python loads files into memory they are about 10 times the size, so this means that with 32GB RAM I should be able to load both results files and the candidates file into memory without issue for faster processing. When I was first trying out Python I made a script to verify that every b value appears in either the candidates file or the factors file (1625443342 from GFN7 did not appear in any file somehow). I did not know of the range() function yet, so I generated a file with all of the b values in it and tried to load that into RAM. It did not go well with an 11GB file, but I kept the script and should be able to modify it to do the residue validation with a little effort :D
OK, I've started making optimal GFN-8 sieve right now, so you'll have less work to do.
This is very much appreciated. I will finish what is running now then run the DC with the better files. GFN8 is where things really slow down, so a smaller file saves a lot of time.
Thanks again and I'll send links for the other files as they become available!
| |
|
streamVolunteer moderator Project administrator Volunteer developer Volunteer tester Send message
Joined: 1 Mar 14 Posts: 1033 ID: 301928 Credit: 543,624,271 RAC: 5,083
                         
|
I am glad to hear that the factor files were useful. For the sieving efforts I sieved ranges from p=~147M-100G, then p=100G-10T, then p=10T+ in one or more separate files. I will not send the 147M-10T files, and will remove everything less than 30T from the remaining files and send them for each GFN as soon as they are ready.
It's OK to send 10T+ files as is, no need spend your time and remove small factors manually unless they took too much space on your Google Drive. A program which removes factors will handle duplicates without problems.
OK, I've started making optimal GFN-8 sieve right now, so you'll have less work to do.
This is very much appreciated. I will finish what is running now then run the DC with the better files. GFN8 is where things really slow down, so a smaller file saves a lot of time.
GFN8 seems to be more difficult beast, it lacks small factors in the beginning of sieving. Smallest ones are 15*29+1 and 21*29+1, this mean that significantly less candidates were removed on first steps of sieve (comparing to GFN-6 and GFN-7). Let's see if deeper sieving could compensate it.
| |
|
|
It's OK to send 10T+ files as is, no need spend your time and remove small factors manually unless they took too much space on your Google Drive. A program which removes factors will handle duplicates without problems.
My Google Drive is just the 15GB free version, but it is still OK. I will just delete old files as they are no longer needed to make space for new stuff as we move along :)
OK, I've started making optimal GFN-8 sieve right now, so you'll have less work to do.
This is very much appreciated. I will finish what is running now then run the DC with the better files. GFN8 is where things really slow down, so a smaller file saves a lot of time.
GFN8 seems to be more difficult beast, it lacks small factors in the beginning of sieving. Smallest ones are 15*29+1 and 21*29+1, this mean that significantly less candidates were removed on first steps of sieve (comparing to GFN-6 and GFN-7). Let's see if deeper sieving could compensate it.
[/quote]
Sounds good! I had originally sieved GFN8 to 1P, but went to 2P for this reason, not really expecting that there would be such a significant slowdown going from GFN7 to GFN8 for the actual testing. I can set up the sieve with multiple cores this weekend and send factor files early next week if it helps. If you are planning on some deeper sieving yourself, let me know the range you are planning on and I will make sure that our efforts don't overlap ;)
My candidates file for GFN8 has 258,073,364 candidates. GFN9 is at 249.5 million candidates and 8.5P depth and GFN10 is at 266.5 million candidates and 13.1P depth right now. From a processing-time standpoint GFN9 has almost reached optimal, but I can take it farther if it helps. GFN10 likely needs to go farther than the 30P I had originally intended. It is quite far from optimal. | |
|
robish Volunteer moderator Volunteer tester
 Send message
Joined: 7 Jan 12 Posts: 2213 ID: 126266 Credit: 7,531,967,424 RAC: 3,351,164
                               
|
I've got GFN7 candidate files 1 to 19 complete or running but having trouble with the 20th candidate file. So I'm downloading the lot again.
I'll keep you informed.... :)
____________
My lucky number 10590941048576+1 | |
|
|
For GFN8 we have the interesting property that already prime number nine, namely 2116^256 + 1, can really be "simplified" to a GFN9, namely 46^512 + 1.
In ancient days I suggested Yves put square brackets around 2116 on this page, if I recall correctly.
/JeppeSN | |
|
|
I've got GFN7 candidate files 1 to 19 complete or running but having trouble with the 20th candidate file. So I'm downloading the lot again.
I'll keep you informed.... :)
Wow... that was fast!! You made some pretty quick work of GFN7!
Let me know how you feel about some GFN8 testing and I can let you know which ranges I haven't done a second run of, or you can just do them all with Stream's candidates files if you want for a complete DC like we did with GFN7. Stream's files will have way fewer candidates than mine did, so it should not take too long either :) | |
|
|
For GFN8 we have the interesting property that already prime number nine, namely 2116^256 + 1, can really be "simplified" to a GFN9, namely 46^512 + 1.
In ancient days I suggested Yves put square brackets around 2116 on this page, if I recall correctly.
/JeppeSN
True! I was curious why the brackets were there, but it seems that every square number is a candidate for having this property. When all GFN testing is done I will write a script to find these values. Maybe they have some interesting patterns or maybe it is just random. I look forward to finding out :) | |
|
robish Volunteer moderator Volunteer tester
 Send message
Joined: 7 Jan 12 Posts: 2213 ID: 126266 Credit: 7,531,967,424 RAC: 3,351,164
                               
|
I've got GFN7 candidate files 1 to 19 complete or running but having trouble with the 20th candidate file. So I'm downloading the lot again.
I'll keep you informed.... :)
Wow... that was fast!! You made some pretty quick work of GFN7!
Let me know how you feel about some GFN8 testing and I can let you know which ranges I haven't done a second run of, or you can just do them all with Stream's candidates files if you want for a complete DC like we did with GFN7. Stream's files will have way fewer candidates than mine did, so it should not take too long either :)
Got the last one going, prob unpacking llrgui was the problem, yeah sure, let me know what you want me to check 👍
____________
My lucky number 10590941048576+1 | |
|
|
So it looks like Rob is good to do the GFN8 second pass! This is fantastic, and with this news I will cancel my own second pass and instead put those resources towards sieving. I plan to sieve to 5P this weekend and can sieve deeper throughout next week if it would be beneficial. That should save a few million candidates from needing to be tested.
I will post factor files later this weekend ;) | |
|
|
GFN1-5 are completed and either double or triple checked with the PARI/GP script, LLR, or both.
Below are links for comprehensive lists of prime b values for each of these N values for anyone interested:
GFN1:https://drive.google.com/open?id=1dLGypMgI6LEf00UiMbgQUU5K9nFwk_r2
GFN2:https://drive.google.com/open?id=166asD5omJO_SvHfXruHrUmAEpMKIWi_G
GFN3:https://drive.google.com/open?id=1deX2w6Tt6s_yA_FYqlvvNZqCKd3JuKgA
GFN4:https://drive.google.com/open?id=1ya3EnygKi3v4UrfVZWkxuiCFALRQdP7V
GFN5:https://drive.google.com/open?id=13Z2FCOrojW_V2aiy_dN53tXN3ch1mj8S
And some stats for fun :)
+---+-------+---------------+--------------+--------------+------------------+--------------------+
| N | b-min | b-max | Expected (E) | Actual (A) | Difference (A-E) | % Diff (A-E)/E*100 |
+---+-------+---------------+--------------+--------------+------------------+--------------------+
| 1 | 2 | 2,000,000,000 | 67422508 | 67420596 | -1912 | -0.003 |
+---+-------+---------------+--------------+--------------+------------------+--------------------+
| 2 | 2 | 2,000,000,000 | 65785508 | 65784460 | -1048 | -0.002 |
+---+-------+---------------+--------------+--------------+------------------+--------------------+
| 3 | 2 | 2,000,000,000 | 25695667 | 25691277 | -4390 | -0.017 |
+---+-------+---------------+--------------+--------------+------------------+--------------------+
| 4 | 2 | 2,000,000,000 | 22539220 | 22544018 | 4798 | 0.021 |
+---+-------+---------------+--------------+--------------+------------------+--------------------+
| 5 | 2 | 2,000,000,000 | 11090019 | 11087394 | -2625 | -0.024 |
+---+-------+---------------+--------------+--------------+------------------+--------------------+
GFN6 and GFN7 are almost finished DC runs so if the original files I posted contain any errors we will know soon. | |
|
|
I'm late to the party...
I'd be willing to run some GFN10, GFN11, GFN12 tests if it were easy enough. I'm putting together a 2nd remodeled Penguin Box with GPUs that would be perfect for this task. At least if it were to be done on a GPU up to 400M. Perhaps after GFN13/14 finish up these could be added to the Private GFN Server as a project? Or are the tasks far too small and the data rate too high to manage?
| |
|
|
I'm late to the party...
I'd be willing to run some GFN10, GFN11, GFN12 tests if it were easy enough. I'm putting together a 2nd remodeled Penguin Box with GPUs that would be perfect for this task. At least if it were to be done on a GPU up to 400M. Perhaps after GFN13/14 finish up these could be added to the Private GFN Server as a project? Or are the tasks far too small and the data rate too high to manage?
That would be awesome, thanks!!
So far Rob and I have been running LLR for everything, so that we can go to b = 2,000,000,000. Also, LLR is much faster than Genefer for the very small GFNs (1-8), because the initialization time is short. There is not a significant difference in run time between Genefer and LLR for GFN9 and GFN10 but the difference is significant by GFN11 and GFN12 (with Genefer being much faster).
Earlier Yves mentioned that it may be possible to modify Genefer to be able to run 16 or 32 parallel tasks on GPU and to exceed the 400M limit (up to 232). If this is possible then I think for GFN9 through GFN12 we will definitely use Genefer as the more parallel tasks you run the smaller the impact of the initialization time is and we may be able to get through them very quickly with GPU testing.
As you mentioned, I would also love it if some of these could be run through the Private GFN Server, especially 11 and 12, but you are right that they are very short and may cause problems with server load, so if Stream does not want to then the way that we have been handling it so far I think is OK. Of course this may be solved if the candidate test files issued by the server contain 16 or 32 values to test, so that there are only 1/16 or 1/32 the number of files, but I am no expert on this, and it is not my server, lol, so I can't really comment :)
So far everything has been done by splitting the candidates files into 20 smaller files and testing them on different computers (or with a combination of PARI/GP and LLR for GFN1-5). After testing, Rob and I were originally planning to perform some pre-processing to isolate the b values and their residues (if not prime) so that we could directly compare the files with a script or software. I did figure out how to compare the residues, but it is quite slow and requires some manual intervention. Stream thankfully offered to write a script to do this directly from the results files, so now the plan is to test two runs of each candidates file for each GFN, compile everything and send it to Stream in a single batch and he will perform the residue and prime validation, as well as checking to make sure that every b value was tested.
Right now the candidates files for GFN8 are being generated again by Stream for Rob to run with LLR (as mine were badly bloated), and the GFN9-12 sieving is still in progress, but once that is finished and GFN9-12 candidates files are ready I will post back here and we can figure out a good distribution of work. The more the merrier for this project, so your help would be much appreciated!
Thanks again, and we'll keep you posted!
Edit: P.S. If your GPUs are thirsty, I recommend a drink from the GFN13 well before it dries up ;) | |
|
Frank Send message
Joined: 30 Dec 17 Posts: 27 ID: 964965 Credit: 481,860,486 RAC: 659,477
                       
|
I am on board. Ideally we would add the project to the private gfn server (if stream wants it as well), but I am also fine with running it privately. | |
|
streamVolunteer moderator Project administrator Volunteer developer Volunteer tester Send message
Joined: 1 Mar 14 Posts: 1033 ID: 301928 Credit: 543,624,271 RAC: 5,083
                         
|
I am on board. Ideally we would add the project to the private gfn server (if stream wants it as well), but I am also fine with running it privately.
It's possible for GFN-12 and probably -11. Other tasks are too short (even in -12 I should send many candidates to test in single WU).
| |
|
|
I am on board. Ideally we would add the project to the private gfn server (if stream wants it as well), but I am also fine with running it privately.
Thanks Frank! Robish is finishing up the last of the GFN8 tests now, and GFN6 and 7 have had both full runs completed and validated. So far, Robish has been doing the other half of the LLR testing, and Stream is now doing the low p sieiving, making the candidates files and doing all residue validation and checks to make sure that every candidate was actually tested twice (ie. pretty much running the show at this point, :) ). I am still taking care of the deep sieving and work distribution.
GFN9 testing with LLR has started and is nearly 25% complete and the GFN11 sieving will be completed in approximately 7 days. I will send you some information shortly in case you are interested in some GFN9 testing with LLR.
It's possible for GFN-12 and probably -11. Other tasks are too short (even in -12 I should send many candidates to test in single WU).
This would be amazing and very much appreciated, and hopefully sending multiple tests would allow the server to not become too overloaded if you did decide to run them with your server. GFN11 tests take ~2s each at b=300M (slightly faster on Turing than previous generations, but no significant difference between previous generations) and GFN12 is taking about 4 seconds each (same b value and same observations as GFN11). Sieving will be completed to 200P on the 11th of April. | |
|
robish Volunteer moderator Volunteer tester
 Send message
Joined: 7 Jan 12 Posts: 2213 ID: 126266 Credit: 7,531,967,424 RAC: 3,351,164
                               
|
Robish is finishing up the last of the GFN8 tests now,
Yeah taking a lot longer than I thought but neeeearly there :)
It's possible for GFN-12 and probably -11. Other tasks are too short (even in -12 I should send many candidates to test in single WU).
That would be cool stream :)
____________
My lucky number 10590941048576+1 | |
|
Yves Gallot Volunteer developer Project scientist Send message
Joined: 19 Aug 12 Posts: 820 ID: 164101 Credit: 305,989,513 RAC: 1,728

|
Sieving will be completed to 200P on the 11th of April.
I wrote a GFN sieve https://github.com/galloty/gfsieve that runs 100% on GPU (CPU load = 0).
On a GTX 1050, GFN-12 sieve rate is 24 P/day. Maybe it can be used to extend GFN-12 sieving. The rate on a GTX-2080 should be > 100 P/day.
| |
|
|
Sieving will be completed to 200P on the 11th of April.
I wrote a GFN sieve https://github.com/galloty/gfsieve that runs 100% on GPU (CPU load = 0).
On a GTX 1050, GFN-12 sieve rate is 24 P/day. Maybe it can be used to extend GFN-12 sieving. The rate on a GTX-2080 should be > 100 P/day.
I took a look at the code last week and did see that it would permit sieving as low as GFN12, but I can't figure out how to combine all of those files into a program that I can run. I am not particularly savvy with that sort of thing. Are you planning on releasing an executable version of this at any point?
There is no rush for GFN12 sieving as my GPUs are all happily working away on GFN13 and my CPUs are either doing GFN11 sieving or GFN9 testing, but if there will someday be an executable version of your sieve I will definitely use that for GFN12, thanks! | |
|
Yves Gallot Volunteer developer Project scientist Send message
Joined: 19 Aug 12 Posts: 820 ID: 164101 Credit: 305,989,513 RAC: 1,728

|
A binary for Windows of gfsieve is available here.
This version is based on 96-bit arithmetic. I will generate a new version where 64-bit arithmetic is used if p <= 9223 P (2^63).
You can compute the number of remaining candidates with the following formula:
#candidates = e-gamma · Cn · Bmax / log(pmax)
where e-gamma = 0.5614595, C10 = 8.0193435, C11 = 7.2245969, C12 = 8.4253499 and Bmax = 2·109.
Sieving must be extended for GFN-10, GFN-11 and GFN-12: if pmax = 200P, a sieve on GPU is able to test 100P / day and in 200P-300P, 2,000,000 candidates are removed. The rate is about 25 removals / seconde.
The optimal sieve limit should be around 10000P/100000P (depending on n). | |
|
|
A binary for Windows of gfsieve is available here.
This version is based on 96-bit arithmetic. I will generate a new version where 64-bit arithmetic is used if p <= 9223 P (2^63).
You can compute the number of remaining candidates with the following formula:
#candidates = e-gamma · Cn · Bmax / log(pmax)
where e-gamma = 0.5614595, C10 = 8.0193435, C11 = 7.2245969, C12 = 8.4253499 and Bmax = 2·109.
Sieving must be extended for GFN-10, GFN-11 and GFN-12: if pmax = 200P, a sieve on GPU is able to test 100P / day and in 200P-300P, 2,000,000 candidates are removed. The rate is about 25 removals / seconde.
The optimal sieve limit should be around 10000P/100000P (depending on n).
Many thanks Yves! This is great!!
I will download and start running this now on a GTX1660 and a GTX 1080ti and see how performance is for GFN11 on those two GPUs. | |
|
|
Wow. This sieve is FAST! This will free up a ton of CPU resources to power through the rest of GFN9 and will make GFN10 viable for going to b=2G, as it had not yet been decided how GFN10 would be tackled. Now we can do up to 400M with Genefer as I was leaning towards, but the remaining portion to 2G can be done with LLR.
I think GFN11 is still too big to take to 2G with LLR, so we will stick with 400M and Genefer for that and GFN12.
Thanks again! | |
|
Yves Gallot Volunteer developer Project scientist Send message
Joined: 19 Aug 12 Posts: 820 ID: 164101 Credit: 305,989,513 RAC: 1,728

|
A new binary is available (gfsieve 0.5.0).
A 64-bit mode was added for p < 2^63 (9223 P).
The speed improvement with 64-bit arithmetic is about 60%.
Good luck with huge files! | |
|
robish Volunteer moderator Volunteer tester
 Send message
Joined: 7 Jan 12 Posts: 2213 ID: 126266 Credit: 7,531,967,424 RAC: 3,351,164
                               
|
A new binary is available (gfsieve 0.5.0).
A 64-bit mode was added for p < 2^63 (9223 P).
The speed improvement with 64-bit arithmetic is about 60%.
Good luck with huge files!
Merci Yves, much appreciated 👍
____________
My lucky number 10590941048576+1 | |
|
|
A new binary is available (gfsieve 0.5.0).
A 64-bit mode was added for p < 2^63 (9223 P).
The speed improvement with 64-bit arithmetic is about 60%.
Good luck with huge files!
Amazing, many thanks good sir! This will be put to very good use :) | |
|
Yves Gallot Volunteer developer Project scientist Send message
Joined: 19 Aug 12 Posts: 820 ID: 164101 Credit: 305,989,513 RAC: 1,728

|
# P/day was not correct when p_max - p_min > 1.
Computations and results were correct, only the displayed value was wrong.
This is fixed in gfsieve 0.5.1 | |
|
Frank Send message
Joined: 30 Dec 17 Posts: 27 ID: 964965 Credit: 481,860,486 RAC: 659,477
                       
|
# P/day was not correct when p_max - p_min > 1.
Computations and results were correct, only the displayed value was wrong.
This is fixed in gfsieve 0.5.1
Perfect, I like it a lot! Is there also a way of saving at what P you are upon closing the sieve and continuing from that checkpoint when you resume? That would be fantastic! | |
|
|
# P/day was not correct when p_max - p_min > 1.
Computations and results were correct, only the displayed value was wrong.
This is fixed in gfsieve 0.5.1
Great, thanks! I noticed that, but was going to let it run a bit longer before pointing it out, in case there were other things too.
Nothing else strange so far except that I do get OpenCL invalid command queue errors when trying to run more than once instance per GPU sometimes. GPU usage is 100%, so more than one instance isn't necessary from that standpoint, but I was running two to prevent thermal cycling of the GPU during the time when the factors are written to file and usage drops to 0%. For the lower p values the factor write time is long enough for the GPU to cool 20-30 degrees which can be hard on the core, but at higher p values the time is short and not problematic. Past about 1000P the factor write time is short enough that the CPU only cools about 5 degrees before running at 100% again so I am only running one instance.
I haven't stopped a run in the middle, but if you did put some kind of checkpoint in for future releases like Frank mentioned that would be great.
Overall this is fantastic, and the 64-bit version will help us make quick work of the GFN10 and GFN11 sieves, where the majority of sieving is in that range :) | |
|
Yves Gallot Volunteer developer Project scientist Send message
Joined: 19 Aug 12 Posts: 820 ID: 164101 Credit: 305,989,513 RAC: 1,728

|
gfsieve 0.6.0:
- save and restore checkpoint
- doesn't display factors on the screen by default. The command line -p can be selected to print them.
- save factors on disk within a separate thread. GPU will stay hot :o)
GPU load is 100% and GPU-MCU load is about 1% then I don't think that running more than once instance would be helpful.
Note that the minimum value for p is 1P. The number of factors is so large in 0-1P that it's more efficient to test this range on CPU.
gfsieve doesn't double-check the divisibility of GFNs. Normally another program is used for this task. It can be a Pari-gp program or a small C code compiled with a multiple precision arithmetic library (GMP, libtommath, NTL, boost multiprecision, ...). | |
|
|
gfsieve 0.6.0:
- save and restore checkpoint
- doesn't display factors on the screen by default. The command line -p can be selected to print them.
- save factors on disk within a separate thread. GPU will stay hot :o)
GPU load is 100% and GPU-MCU load is about 1% then I don't think that running more than once instance would be helpful.
Note that the minimum value for p is 1P. The number of factors is so large in 0-1P that it's more efficient to test this range on CPU.
gfsieve doesn't double-check the divisibility of GFNs. Normally another program is used for this task. It can be a Pari-gp program or a small C code compiled with a multiple precision arithmetic library (GMP, libtommath, NTL, boost multiprecision, ...).
Fantastic, thanks!! GPU staying hot is precisely what I was looking for when I ran two instances for the low p values, so this is perfect and 1 instance will be good now. I worry about thermal cycling a lot more than I worry about absolute temperature (well, unless it starts getting into the 80C range; then its time to fix that).
This program has changed optimal sieve depths for things by an enormous amount. Even GFN13, which is almost finished, can still benefit from additional sieving (and will be sieved by over 2,000P father than original sieve in about 8 hours). GFN14 can benefit significantly (and is also being sieved much deeper than initially). For GFN10 it has made LLR testing to b=2G viable, where it likely would not have been before.
You're a miracle worker with this program Yves. Can't say thanks enough :) | |
|
Honza Volunteer moderator Volunteer tester Project scientist Send message
Joined: 15 Aug 05 Posts: 1957 ID: 352 Credit: 6,150,917,438 RAC: 2,308,002
                                      
|
Trouble running gfsieve 0.6.0 for low min p value.
It ends with error: Internal error detected.
Same for parameters 12 1 2
Same for parameters 17 1 2
But works for for parameters 17 100 101
But works for for parameters 17 10 11
But works for for parameters 17 2 3
But works for for parameters 12 2 3
d:\TeMp\___PG\gfsieve-win32-0.6.0>gfsieve.exe 14 1 2 -p
gfsieve 0.6.0 win32 gcc-9.3.0
Copyright (c) 2020, Yves Gallot
gfsieve is free source code, under the MIT license.
0 - device 'GeForce RTX 2080', vendor 'NVIDIA Corporation', platform 'NVIDIA CUDA'.
Running on device 'GeForce RTX 2080', vendor 'NVIDIA Corporation', version 'OpenCL 1.2 CUDA' and driver '445.75'.
46 compUnits @ 1860MHz, mem=8192MB, cache=1472kB, cacheLine=128B, localMem=48kB, constMem=64kB, maxWorkGroup=1024.
64-bit mode
globalWorkSize = 2097152, localWorkSize = 64
Testing n = 14 from 999937105985537 to 2000011650891777
terminating...
error: Internal error detected.
____________
My stats | |
|
Yves Gallot Volunteer developer Project scientist Send message
Joined: 19 Aug 12 Posts: 820 ID: 164101 Credit: 305,989,513 RAC: 1,728

|
Trouble running gfsieve 0.6.0 for low min p value.
It ends with error: Internal error detected.
For n = 14, there are 19,879,873 factors in 1P-2P and the size of the buffer was 16,777,216.
Fixed in gfsieve 0.6.1
Note that -p will take time with so many factors! | |
|
Honza Volunteer moderator Volunteer tester Project scientist Send message
Joined: 15 Aug 05 Posts: 1957 ID: 352 Credit: 6,150,917,438 RAC: 2,308,002
                                      
|
Thank, Yves, issue was fixes.
Testing n = 14 from 999937105985537 to 2000011650891777
19879873 factors, time = 00:01:49, 788 P/day
Testing n = 22 from 985162418487297 to 2005509200674817
20387709 factors, time = 00:01:26, 1e+03 P/day
____________
My stats | |
|
|
We are now finished everything up to, and including, GFN8!
Here are the download links for files containing the prime b values for each GFN:
GFN1:https://drive.google.com/open?id=1dLGypMgI6LEf00UiMbgQUU5K9nFwk_r2
GFN2:https://drive.google.com/open?id=166asD5omJO_SvHfXruHrUmAEpMKIWi_G
GFN3:https://drive.google.com/open?id=1deX2w6Tt6s_yA_FYqlvvNZqCKd3JuKgA
GFN4:https://drive.google.com/open?id=1ya3EnygKi3v4UrfVZWkxuiCFALRQdP7V
GFN5:https://drive.google.com/open?id=13Z2FCOrojW_V2aiy_dN53tXN3ch1mj8S
GFN6:https://drive.google.com/open?id=1zM7NPdZHUS1YiXZxwHXKWdZwog0psOqC
GFN7:https://drive.google.com/open?id=1WzGsRSxrXhjUH4UkjzEgf3kMBL04V3Vu
GFN8:https://drive.google.com/open?id=1pSyYwGYItixvkII0h_46gz47cdkHCgD-
GFN9 is ~50% complete, and will be done in the next month or two, but after that there will be a short testing hiatus while the sieving is completed for GFN10-12. With Yves' new sieve we can very likely get GFN10 sieved deep enough to make an LLR search up to b=2G viable, and GFN11 and GFN12 will be run on Genefer.
Many thanks to everyone who has contributed so far! We are making some very solid progress :) | |
|
|
GFN9 is now complete to b=2G!
GFN9 Prime b Values:https://drive.google.com/open?id=1nIFzQtVywesH0y9lBw_-Vbfo7It_9umG
Many thanks to all who contributed to these efforts! This one was much more of a distributed project than the lower GFNs.
Stay tuned for GFN10-12 testing; we have something special in the works that should make it a lot more fun ;) | |
|
Ravi FernandoProject administrator Volunteer tester Project scientist Send message
Joined: 21 Mar 19 Posts: 211 ID: 1108183 Credit: 13,860,596 RAC: 6,886
              
|
Very nice! It looks like there are 1437157 of them. Yves's calculator predicts 1436750, so this is 407 (0.028%, or 0.34 standard deviations) more than expected. | |
|
|
Very nice! It looks like there are 1437157 of them. Yves's calculator predicts 1436750, so this is 407 (0.028%, or 0.34 standard deviations) more than expected.
Bah! Pure coincidence and evil demons' work. I still think there are only finitely many of them. /JeppeSN | |
|
|
Very nice! It looks like there are 1437157 of them. Yves's calculator predicts 1436750, so this is 407 (0.028%, or 0.34 standard deviations) more than expected.
Bah! Pure coincidence and evil demons' work. I still think there are only finitely many of them. /JeppeSN
Aren't we expecting infinitely many primes for fixed exponent and varying base? | |
|
|
Very nice! It looks like there are 1437157 of them. Yves's calculator predicts 1436750, so this is 407 (0.028%, or 0.34 standard deviations) more than expected.
Bah! Pure coincidence and evil demons' work. I still think there are only finitely many of them. /JeppeSN
Aren't we expecting infinitely many primes for fixed exponent and varying base?
Of course, yes; I was trying to be funny. It looks like Yves Gallot's heuristics are accurate. /JeppeSN | |
|
robish Volunteer moderator Volunteer tester
 Send message
Joined: 7 Jan 12 Posts: 2213 ID: 126266 Credit: 7,531,967,424 RAC: 3,351,164
                               
|
Of course, yes; I was trying to be funny.
🤣 I thought it was funny
____________
My lucky number 10590941048576+1 | |
|
|
Very nice! It looks like there are 1437157 of them. Yves's calculator predicts 1436750, so this is 407 (0.028%, or 0.34 standard deviations) more than expected.
GFN9 certainly follows the pattern of being pretty accurately predicted by Yves! Best one so far in terms of absolute error is GFN7, which was off by only 46 (2385773 predicted, 2385819 actual), and best in terms of % error is GFN2, which was off by 0.001593% (65785508 predicted, 65784460 actual). They have all been remarkably good though.
Bah! Pure coincidence and evil demons' work. I still think there are only finitely many of them. /JeppeSN
Totally agreed JeppeSN! With how many have been identified with these small GFN projects I estimate that we've found at least half, maybe as much as two-thirds, of them. We will reach the end one of these days! :P | |
|
|
Well! No posts for a while, but we have been busy with this one and it is certainly time for an update.
GFN9, GFN10 and GFN11 are complete, and all primes verified! There remains some validation efforts for GFN11, but it is expected that those will go through without issue.
The results:
N Actual Expected
9 1437157 1436750
10 770764 769241
11 346725 346503
As you can see, the predictions are extremely close to actual; a fantastic result!
If anyone would like the full list of prime b values for these GFNs they can be found at the following links:
GFN9: https://drive.google.com/file/d/1nIFzQtVywesH0y9lBw_-Vbfo7It_9umG
GFN10: https://drive.google.com/file/d/1etmOlz0emQ0yuoZU-9tv6PEKYO_RhwcS
GFN11: https://drive.google.com/file/d/1l-GXbtCnSJXCCC8gTIe9HDR67WaYK9MZ
With that said, I would like to thank everyone involved in this. Names not listed in any particular order, and I hope that I have not missed anyone. Everybody's efforts are immensely appreciated and it's been a heck of a ride!
First; I'd like to give an enormous thank you to Yves, who has programmed and re-programmed many custom applications dedicated to the small GFN search, without which we would still be years away from finishing what has been done so far.
A massive thank you to Stream too, for doing all of the hard work for candidates file generation from sieve files, low-p sieving, results validation and everything else that requires significant data handling. Without his help, this project would have stalled long ago and the confidence in the results would not be as high as it is today.
Thank you as well to Pavel, who revised LLR2 for the residue validation for GFN10 and GFN11!
And as for the crunching goes; I definitely owe Rob a cookie or two and a hefty pat-on-the-back! Rob has done the other half of GFN7, GFN8 and GFN10, along with much of GFN9 and a good chunk of GFN11. Frank too has done a huge amount of work with GFN9 and GFN11 along with most of the GFN11 sieving, so thank you to you two too!
Many thanks also to Vaughan and Penguin who did a bunch of LLR testing for GFN9 and sieving for GFN11 too! And last but not least, Walli, who sieved GFN12 to optimal depth at 35000P!
And also, thank you to JeppeSN for support for this project from the very beginning. His ideas and suggestions certainly helped get this on the right track.
Again, I hope I have not missed anyone. This has been an amazing project involving many people and significant effort. Something I could not have accomplished alone.
The final bit of news is that GFN12 will be run from the Private GFN Server! This will likely happen after GFN14 is finished, so everyone who wants to run GFN12 should turn their GPUs in that direction and help get GFN14 done asap ;) | |
|
|
A huge congrats on this achievement and to all involved! I will definitely help out with some GFN12 work when it goes online. Will it run on GPUs too or CPUs only?
Also I'm curious about the statistics. Would you mind posting a table of expected and actual number of primes for all N=1 to 11? | |
|
robish Volunteer moderator Volunteer tester
 Send message
Joined: 7 Jan 12 Posts: 2213 ID: 126266 Credit: 7,531,967,424 RAC: 3,351,164
                               
|
Thanks Kellen it was fun and in these strange times, a nice distraction.
However I believe you left yourself out and deserve a huge pat on the back also, as without your infectious enthusiasm and coordination, it would not have happened ;)
Cheers and count me in for the next project you think up (don't care what it is :D )
____________
My lucky number 10590941048576+1 | |
|
robish Volunteer moderator Volunteer tester
 Send message
Joined: 7 Jan 12 Posts: 2213 ID: 126266 Credit: 7,531,967,424 RAC: 3,351,164
                               
|
A huge congrats on this achievement and to all involved! I will definitely help out with some GFN12 work when it goes online. Will it run on GPUs too or CPUs only?
Also I'm curious about the statistics. Would you mind posting a table of expected and actual number of primes for all N=1 to 11?
Table from Yves.
n b_max #primes expected error
1 2·10^9 67420596 67422507.9 -0.0028%
2 2·10^9 65784460 65785508.4 -0.0016%
3 2·10^9 25691277 25695666.7 -0.0171%
4 2·10^9 22544018 22539220.4 +0.0213%
5 2·10^9 11087394 11090018.6 -0.0237%
6 2·10^9 6054548 6051202.4 +0.0553%
7 2·10^9 2385819 2385773.3 +0.0019%
8 2·10^9 2855175 2852679.9 +0.0874%
9 2·10^9 1437157 1436749.6 +0.0283%
10 2·10^9 770764 769240.7 +0.1980%
11 2·10^9 346725 346503.0 +0.0641%
____________
My lucky number 10590941048576+1 | |
|
Renix Send message
Joined: 26 Aug 16 Posts: 346 ID: 455383 Credit: 4,173,411,245 RAC: 5,110,439
                     
|
The final bit of news is that GFN12 will be run from the Private GFN Server! This will likely happen after GFN14 is finished, so everyone who wants to run GFN12 should turn their GPUs in that direction and help get GFN14 done asap ;)
Is GFN12 going to be cpu or gpu? | |
|
|
Hi lots to read here can you let us know how to participate in simple language and easy instructions or best to stick to projects available on primegrid preferences part of the website ? | |
|
|
Is GFN12 going to be cpu or gpu?
The details are generally unknown at this time; but it will likely start off being CPU+GPU and then end being just GPU like other GFN projects, but it may be just GPU the whole time depending on exactly what software is used. We will know closer to the start date :)
Hi lots to read here can you let us know how to participate in simple language and easy instructions or best to stick to projects available on primegrid preferences part of the website ?
The instructions on how to participate will be detailed later, but it will happen on Stream's private server. The instructions on how to join the private server can be found here: https://www.primegrid.com/forum_thread.php?id=7985
Enjoy! | |
|
|
Thanks wasnt as bad as I feared it's now doing GEN14 GPU :) | |
|
|
Thanks wasnt as bad as I feared it's now doing GEN14 GPU :)
Awesome! That was my perception too when I first looked at the post. I thought it would be way harder than it actually was to connect to the server, but it is just as easy as any other BOINC project really :)
Good luck with GFN14! | |
|
|
Table from Yves. ...
Thanks!
Interesting that there are more GFN8 primes than GFN7 primes in your search range :)
And the accuracy of the estimates is quite remarkable.
| |
|
Frank Send message
Joined: 30 Dec 17 Posts: 27 ID: 964965 Credit: 481,860,486 RAC: 659,477
                       
|
Thanks!
Interesting that there are more GFN8 primes than GFN7 primes in your search range :)
And the accuracy of the estimates is quite remarkable.
As expected since F_3=257. For expectations about GFN x see the Cn value from Yves' website, or just type in the bmin/bmin and n value (http://yves.gallot.pagesperso-orange.fr/primes/stat.html) | |
|
Yves Gallot Volunteer developer Project scientist Send message
Joined: 19 Aug 12 Posts: 820 ID: 164101 Credit: 305,989,513 RAC: 1,728

|
As expected since F_3=257. For expectations about GFN x see the Cn value from Yves' website, or just type in the bmin/bmin and n value (http://yves.gallot.pagesperso-orange.fr/primes/stat.html)
Note that the condition is Cn > 2 Cn-1 (because the weight is Cn / 2n).
A Fermat number is not a sufficient condition:
C8 = 7.43... > 2 * (C7 = 3.10...)
but C16 = 11.19... < 2 * (C15 = 5.80...)
n b_max #primes expected error
15 9·10^7 949 924.0 +2.7%
16 9·10^7 920 891.4 +3.2%
I don't think that it is possible to prove that a Fermat number is a necessary condition (because an improbable sequence of primes 3*2n+1, 5*2n+1, ... may exist) but if there is no Fermat prime > F4 then GFN-8/GFN-7 could be the only exception. | |
|
|
Got my 3090 doing the GFN14s, seems to like doing these, runs 20 celcius cooler than when doing other work :)
I saw this page which is refreshed every 6 hours, just wondering is there version that is updated more often ? http://boincvm.proxyma.ru:30080/test4vm/user_profile/gfnxx_all_status.html | |
|
Monkeydee Volunteer tester
 Send message
Joined: 8 Dec 13 Posts: 540 ID: 284516 Credit: 1,532,095,446 RAC: 684,673
                            
|
Got my 3090 doing the GFN14s, seems to like doing these, runs 20 celcius cooler than when doing other work :)
I saw this page which is refreshed every 6 hours, just wondering is there version that is updated more often ? http://boincvm.proxyma.ru:30080/test4vm/user_profile/gfnxx_all_status.html
How long per task and how many tasks at once?
The stats page there is only updated every 6 hours-ish. Sometimes it's a few minutes longer than 6 hours. There's no other site-wide stats page there that I know of.
____________
My Primes
Badge Score: 4*2 + 6*2 + 7*3 + 8*10 + 11*3 + 12*1 = 166
| |
|
|
was running 4 tasks at about 40 seconds each. task manager shows 100% utilisation so left at 4 | |
|
Renix Send message
Joined: 26 Aug 16 Posts: 346 ID: 455383 Credit: 4,173,411,245 RAC: 5,110,439
                     
|
I run either 6 or 8 tasks on 1660ti's. The time increases a bit but it isn't going to impact you much. I also run the same on 2070's. 0.01 is what I use for days of work downloaded onto my systems. That will keep you going through some times when the server takes a little longer to send out more tasks. All in all the site is pretty dependable. The tasks are short so the gpu's aren't worked as hard as on the larger GFN tasks. And yes, every 6 hours for updating the stats. | |
|
|
cool cheers will do 8 tasks | |
|
|
OK don't know what I have done but BOINC doesnt recognise GFN14 any more not sure if perhaps I have been blacklisted sorry if I have broken something (had to do some resets and aborts) or is something wrong with this ? I changed 0.25 to 0.125 for 8 tasks ?
<app_config>
<app_version>
<app_name>gfn14</app_name>
<plan_class>opencl_nvidia_gfn_101</plan_class>
<avg_ncpus>0.01</avg_ncpus>
<ngpus>0.125</ngpus>
<cmdline>-x ocl4</cmdline>
</app_version>
</app_config>
PRIVATE GFN SERVER: Notice from BOINC
Your app_config.xml file refers to an unknown application 'gfn14'. Known applications: None
| |
|
|
got it running again cheers :) | |
|
Message boards :
Generalized Fermat Prime Search :
GFN1 - GFN12 Status |