mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Software

Reply
 
Thread Tools
Old 2008-08-10, 10:03   #1
lavalamp
 
lavalamp's Avatar
 
Oct 2007
London, UK

52516 Posts
Default 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
File Type: zip sieves_of_fail.zip (805 Bytes, 91 views)
lavalamp is offline   Reply With Quote
Old 2008-08-10, 12:28   #2
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

136328 Posts
Default

It is already known. It is rare, but can happen.
rogue is online now   Reply With Quote
Old 2008-08-10, 13:25   #3
lavalamp
 
lavalamp's Avatar
 
Oct 2007
London, UK

3×439 Posts
Default

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.
lavalamp is offline   Reply With Quote
Old 2009-01-13, 01:27   #4
Kosmaj
 
Kosmaj's Avatar
 
Nov 2003

70468 Posts
Default

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
Click image for larger version

Name:	newpgen.png
Views:	145
Size:	17.5 KB
ID:	3175  

Last fiddled with by Kosmaj on 2009-01-13 at 01:33
Kosmaj is offline   Reply With Quote
Old 2009-01-13, 01:50   #5
lavalamp
 
lavalamp's Avatar
 
Oct 2007
London, UK

3×439 Posts
Default

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.
lavalamp is offline   Reply With Quote
Old 2009-01-14, 07:41   #6
lavalamp
 
lavalamp's Avatar
 
Oct 2007
London, UK

52516 Posts
Default

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.
lavalamp is offline   Reply With Quote
Old 2009-01-14, 13:46   #7
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

2×3×19×53 Posts
Default

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 sr<x>sieve is much faster.
rogue is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
NewPgen Cybertronic Factoring 0 2014-03-22 10:07
Any answers on missing factors? schickel Aliquot Sequences 8 2011-11-29 12:24
Missing factors at the 'Known Factors' page MatWur-S530113 PrimeNet 11 2009-01-21 19:08
Dumb question about missing srsieve factors robo_mojo Riesel Prime Search 4 2008-04-22 04:37
Missing factors henryzz Math 10 2007-12-08 12:45

All times are UTC. The time now is 23:53.

Thu Dec 3 23:53:45 UTC 2020 up 20:05, 1 user, load averages: 1.30, 1.29, 1.26

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.