mersenneforum.org NewPGen missing factors?
 Register FAQ Search Today's Posts Mark Forums Read

2008-08-10, 10:03   #1
lavalamp

Oct 2007
London, UK

22×3×109 Posts
NewPGen missing factors?

Recently I wrote some code to sort factors into files by order of magnitude of two (it does other things to, but that's the jist of it), just so I could see the rate of removal of candidates. While doing this I found a few gaps where I must have lost/deleted factor files, so I re-sieved bits to fill them in.

Now when I first started sieving I used NewPGen, but I have since converted to using sr[125]?sieve for their unearthly speed gains.

In re-sieving some parts, I have in places re-sieved areas that I do have factor files for (in particular, NewPGen.del files). And because of that I've noticed that NewPGen seems to miss factors every so often.

I don't know exactly how often since I've not written any code to compare two factor files and record differences, however I do have three that I found by comparing manually:

126737437907 | 27*2^1008502-1
889968919247 | 27*2^1084858-1
1068394351859 | 27*2^1032544-1

If I create a sieve file with only 1 candidate in, for example:
Code:
889968919000:M:0:2:258
27 1084858
Then NewPGen will not find the factor for any of them.

If I create a sieve file with all three candidates in the file, and I set the current sieve depth to just below the factor for n = 1032544 or 1084858, it will find factors for them, but it will not find a factor for n = 1008502.

It seems that NewPGen is no longer updated, so this bug may well become a feature. If it was already known that NewPGen missed factors sometimes then I apologise for resurrecting a known issue, but it wasn't known to me, and I did look first.

I've uploaded the sieve files in case anyone would like to check. And I should mention that I have checked, double checked and triple checked that these factors are correct.
Attached Files
 sieves_of_fail.zip (805 Bytes, 86 views)

 2008-08-10, 12:28 #2 rogue     "Mark" Apr 2003 Between here and the 5,953 Posts It is already known. It is rare, but can happen.
 2008-08-10, 13:25 #3 lavalamp     Oct 2007 London, UK 130810 Posts Hm, I wouldn't say it's so rare, here are 15 in a fairly narrow range: Code: 69560891419 | 27*2^3754541-1 80755283783 | 27*2^2028362-1 101023290923 | 27*2^2125354-1 115696282571 | 27*2^3768772-1 126737437907 | 27*2^1008502-1 * 157858090463 | 27*2^2253520-1 159606525097 | 27*2^1924441-1 174490280303 | 27*2^1034662-1 184054693681 | 27*2^1377133-1 184862537749 | 27*2^1404844-1 194858058313 | 27*2^3677072-1 199505104811 | 27*2^3713438-1 240836291929 | 27*2^1240910-1 248957641741 | 27*2^3879850-1 254616018287 | 27*2^2451848-1 The one that is starred is one of the ones from the previous post.
 2009-01-13, 01:27 #4 Kosmaj     Nov 2003 2×1,811 Posts Your claims are wrong. I just did some tests and successfully sieved out 5 numbers from your posts. Code: p=69560891419 divides n=3754541 p=80755283783 divides n=2028362 p=184054693681 divides n=1377133 p=184862537749 divides n=1404844 p=1068394351859 divides n=1032544 And I'm enclosing a screen-shot for the two at 184bn. Your hardware is unstable or somehow you mishandled the software options. Note that "Verify Results" should be checked. There have been many claims similar to yours but the great majority turned out to be wrong. I'm not saying that NewPGen never ever misses a factor but it's on a much lower scale than you are suggesting. Attached Thumbnails   Last fiddled with by Kosmaj on 2009-01-13 at 01:33
 2009-01-13, 01:50 #5 lavalamp     Oct 2007 London, UK 24348 Posts Fair enough, I'll go back and check the cases I mentioned, but whether or not it misses a factor seems to vary depending on other candidates in the sieve.
 2009-01-14, 07:41 #6 lavalamp     Oct 2007 London, UK 22·3·109 Posts OK, I started a sieve in NewPGen for 27*2^n-1 where 1,000,000 <= n <= 4,000,000. I ran the sieve until 137,438,953,472 (2^37). (If it makes any difference, I manually stopped the sieve at 11 billion, then started it up again with the 2^37 limit.) First of all, the five factors below 2^37 which it missed previously, which I reported in my second post in this thread, were found. This immediately throws suspicion on the hardware running the first sieve. But, on this sieve, NewPGen missed the following four factors: Code: 26619935267 | 27*2^2010870-1 64078413029 | 27*2^2250997-1 95031956891 | 27*2^2328458-1 112509769129 | 27*2^2483378-1 This then also throws suspicion on the current hardware running this sieve (which is different to the system that ran the last sieve, this system is only about a month old and still has that new PC smell). However, if I edit the top line of the sieve file to just before any of the four known factors missed, and run NewPGen again on that file, it doesn't find them. I have tried this on two systems and it misses them on both. One a 4.2 GHz i7 system with Vista SP1 64 bit, the other a P4 1.7 GHz running XP SP2 32 bit. In my mind this then suggests it is not a hardware problem, but a bug in NewPGen. As I said in my previous post, the factors missed also seem to depend on other candidates in the sieve file. Unfortunately it would be quite difficult to replicate the first sieve (which I ran over a year ago) as I started sieving a range, then broke bits off and at some point extended the n range. So then perhaps someone would like to try running the same sieve I just ran on an AMD or VIA CPU. I have uploaded the outputted sieve file from NewPGen here.
 2009-01-14, 13:46 #7 rogue     "Mark" Apr 2003 Between here and the 5,953 Posts You are beating a dead horse. As stated here and in other places, NewPGen can miss factors. It due to how the BSGS algorithm is implemented. I suspect that if you choose different values for min n and max n that it will find those factors, but miss others. Also stated here and elsewhere is that NewPGen should not be used for sieving these sequences as srsieve is much faster.

 Similar Threads Thread Thread Starter Forum Replies Last Post Cybertronic Factoring 0 2014-03-22 10:07 schickel Aliquot Sequences 8 2011-11-29 12:24 MatWur-S530113 PrimeNet 11 2009-01-21 19:08 robo_mojo Riesel Prime Search 4 2008-04-22 04:37 henryzz Math 10 2007-12-08 12:45

All times are UTC. The time now is 15:10.

Wed Oct 28 15:10:28 UTC 2020 up 48 days, 12:21, 4 users, load averages: 1.44, 1.87, 1.98