Algebraic factors in sieve files

[LaurV]

Originally Posted by Batalov

No adult male should skip on that activity!

Ha ha ha ha Serge, I can't stop laughing...

busted! You totally got me here...
One more proof that the typos are cleverer than us... They squeeze themselves in the most unexpected places, to produce maximum damages...

[gd_barnes]

Originally Posted by rogue

Serge found a bug that causes it to crash for large ranges of n. I tested on smaller ranges of n, thus didn't trigger it. It has been fixed and the link has the current code and Windows build.

No surprise. Typical lack of a test plan. Did you do any parallel tests? Likely not. Do you know what a parallel test is? Doubtful. I have never heard of you running one.

If the project loses some people as a result of this exchange between Mark and me then so be it. He and I have had words before about a lack of parallel testing of changes to PRPnet, PFGW, and srsieve that have created many problems for the project. I have never seen a good parallel test done on any changes that are made. It is intolerable in a very exacting project that software updates are introduced without proper testing procedures.

As I stated in my last post, if correct parallel testing vs. a known correct version of srsieve cannot be demonstrated then CRUS will refuse to accept any new work with the new program. If other projects want to run their efforts on an improperly tested program that is their choice but it is not ours.

[gd_barnes]

Originally Posted by LaurV

Now slow down a little...

I am myself adept of "if it works do not fix it", and gave a +1 above to pepi's suggestion. But OTOH, I would like to have a new version of srsieve which is more efficient (and eventually removes the "all candidates are divisible by 2" bullshit or let us skip it intentionally with a command line switch, or better offer command line switches for removing algebraic factors too). In that case, I am willing to be part of testing team, to do comparison testes as Gary suggested. And trust me, I do that testing activity for a living, if it is something good to say about a product, I may "forget" to say it, but if it is something to criticize, I am your man, I will always say it

Yes, please remove the "all candidates are divisible by 2" check in srsieve. That will allow us to sieve certain repeat-digit forms that are not currently sievable as a result of the check.

Oh...and as you can tell...I will definitely be the man to criticize improper changes. They used to call me the code breaker at my legacy programming job. My main job was to create tests that broke programs. That is why I get so irritated at a lack of test plans on these code changes.

[gd_barnes]

Originally Posted by rogue

CRUS is not the only user of srsieve. if CRUS chooses to use another program or some older version of srsieve, it is their choice.

I have posted an updated version of srsieve here. Here are the release notes:

  Rewrote code to find algebraic factorizations so that more can be caught.  It will search for:
     GFNs -> where k*b^n+1 can be written as x^m+1
     Trivial -> where k*b^n-1 can be written as x^m-1
  which will remove all terms for the sequence.

  These algebraic factorizations are now written to algebraic.out so that they can be verified with pfgw:
     where k*b^n+1 can be written as x^q*y^r+1 and r%q=0 and q is odd
     where k*b^n-1 can be written as x^q*y^r-1 and r%q=0
     where k*b^n+1 can be written as x*2^m+1 and m%4=2
     where k*b^n+1 can be written as 4*x^z*y^m+1 and z%4=0 and m%4=0

Note the second section. One can now verify the algebraic factors found by srsieve. I have run a few tests and haven't found any bugs, but that doesn't mean that there aren't any, but they will reveal themselves when running algebraic.out thru pfgw.

In this new release, it is smart enough to deteremine if k and b have the same root, i.e. k = m^x and b = m^y so that it can more easily identify GFN and Trivial forms.

For the first two forms, those algebraic factors are not written to algebraic.out. For GFNs, it doesn't mean that it has a factor, but that if you truly want to sieve GFNs, use gfnsieve, not srsieve.

For the first two forms logs to algebraic.out, it factorizes k and b and can find factorizations where they share a common factor. The previous release could not do that.

I suspect that the last two might have some generalizations, but I haven't investigated.

If Serge or others discover additional algebraic forms, please share and I will incorporate as best I can.

I ran a couple of parallel tests on forms with no algebraic factors. No differences were found. But many more parallel tests are needed.

I then ran the form 8*86^n+1 for n=1 to 100e3 to P=100e6. This was the very first test that I ran of a form with algebraic factors. On the command line window it showed:

Removed 33333 algebraic factors for 8*86^n+1 as 8=2^3
Removed 33334 algebraic factors for 8*86^n+1 as 8*86^6=14792^3

The first line makes perfect sense to me as it is removing all n==(0 mod 3). The second does not. Further investigation shows that it is removing all n==(1 mod 3). This is obviously not correct so I looked in the algebraic.log file to see if I was not understanding something. Here is a copy-paste about halfway down where it finished showing the 8=2^3 factors and began showing the 8*86^6=14792^3 factors:

(2*86^33330+1) | 8*86^99990+1
(2*86^33331+1) | 8*86^99993+1
(2*86^33332+1) | 8*86^99996+1
(2*86^33333+1) | 8*86^99999+1
(14792*86^1431655763+1) | 8*86^1+1
(14792*86^1431655764+1) | 8*86^4+1
(14792*86^0+1) | 8*86^7+1
(14792*86^1+1) | 8*86^10+1
(14792*86^2+1) | 8*86^13+1
(14792*86^3+1) | 8*86^16+1
(14792*86^4+1) | 8*86^19+1
(14792*86^5+1) | 8*86^22+1

First problem:
Checking in the factordb confirmed that none of these "14792*86^n+1" factors is correct. It showed that the factor of 14792*86^n+1 is actually a factor of 8*86^(3n+6)+1 meaning that the factor of 14792*86^n+1 is nothing more than an elaborate form of 8*86^(3n)+1. In other words 14792*86^n+1 should only remove n==(0 mod 3) but that is already removed by 8*86^(3n)+1 so...14792*86^n+1 is not something that should even be considered.

Second problem:
14792*86^1431655763+1 is obviously not a factor of 8*86^1+1. Serious display problem there.

I then ran 8*86^n+1 with my favorite old known bugfree version of srsieve. Of course it left quite a few "bad" pairs that are n==(0 mod 3) but it left FAR more "good" pairs that are n==(1 mod 3) in the file.

Mark, I think the code needs a whole lot of work and testing. This is the kind of problem that caused the program to incorrectly remove many good k/n pairs before when you were working on removing the algebraic factors for squares.

I hope this demonstrates why I am so frustrated with the lack of testing. As a project admin I should not have to test every program change that comes our way but it looks like I have no choice. In this case even if you fix this problem I can't help but wonder how many other problems like this that there are in the code. An extensive test plan is needed to test every change that you made in multiple ways.

[rogue]

I ran a number of tests, especially ones pointed out by Serge, but it is not possible for me to test every possible combination. If someone will provide a list of k*b^n+c for me to test with, I will gladly do so.

As I stated previously a quick verification of the algebraic factors can be done by running algebraic.log thru pfgw.

BTW, this was caused by an underflow, i.e. an unsigned value that went below 0.

[gd_barnes]

Originally Posted by rogue

I ran a number of tests, especially ones pointed out by Serge, but it is not possible for me to test every possible combination. If someone will provide a list of k*b^n+c for me to test with, I will gladly do so.

As I stated previously a quick verification of the algebraic factors can be done by running algebraic.log thru pfgw.

BTW, this was caused by an underflow, i.e. an unsigned value that went below 0.

Really?

It doesn't require that you test every possible combination. Just a very basic test would have caught these problems. That was the very first simple algebraic test that I tested after running a couple of parallel tests for bases without algebraic factors.

Nothing needs to be run through anything to see that 14792*86^n+1 does not remove n==(1 mod 3) from 8*86^n+1. 14792=86^3 so it is just another form of k=q^3, which removes n==(0 mod 3). Surely this is obvious to you. 14792*86^n+1 should not even be considered because 8*86^(3n)+1 already has 2*86^n+1 has a factor, which removes n==(0 mod 3).

The 1st and main problem is that it is removing all n==(1 mod 3). Take a look at what I posted and see for yourself.

Of course the display issue in the algebraic factors files is an underflow problem. The display issue is the 2nd problem that I pointed out.

There is no reason for me or anyone else to test anything else when such a blatant error exists in the code. n==(0 mod 3) should be removed. n==(1 mod 3) should not.

I suggest that you test 8*86^n+1 and post a new program when these two problems for this one test have been fixed. No one here will trust your code if it can't pass such a simple test. k=q^3 is one of the easiest cases.

[rogue]

Ok. I've taken the new routines and compiled them outside of srsieve and ran thru k from 1 to 1050 and b from 2 to 1050 and n from 1 to k + 10 for both +1 and -1 forms. It pumped out over 43e6 algebraic factors that I used pfgw to verify. This revealed three bugs which should now be fixed (presuming I patched sriseve correctly). The source and executable have been posted.

[gd_barnes]

Sounds like a lot of good testing.

Features on GFN's:

1. Do we really want to completely remove GFN's from sieving? Some people may want to sieve for them. I realize that srsieve is not the best siever for them but completely removing GFN's gives the impression that they are always composite, which is not the case. My suggestion is to remove your code for GFN's and let the program sieve them like it always has.

2. It did not write anything to algebraic.log about the removal of the GFN. Should it be doing that?

So far I've tried a lot of different powers including k's with multiple powers (such as k=2^30) and it looks good. I still have plenty of parallel testing to go.

[gd_barnes]

Some bugs:

1. It continues trying to sieve a sequence even if all terms have been removed and it doesn't seem to go very fast even though no terms remain. The same problem occurs for both algebraic factors and GFNs. When finished it just writes a file with the standard header line and nothing else. This could result in quite a bit of extra CPU time if the sieve depth is deep. Examples: 8*1000^n+1 or 10*1000^n+1.

2. It crashes every time I try to feed it an already sieved file. Old srsieve had no problem with this. I even tried random sieve files with no algebraic factors and it still crashed. We need to be able to feed it our existing sieve files and have it remove algebraic factors for us. Also for other projects such as repeat-digit sequences where c not = 1 or -1 neither sr1sieve nor sr2sieve can be used for additional sieving. Example sieve file: http://www.noprimeleftbehind.net/cru...-100K-400K.txt

Question:

If we're doing this, shouldn't we go all the way with it? I think that others have made that statement in this thread. Why are only c=1 and -1 being considered for algebraic factors? For example srsieve can easily sieve 4*6^n-121. 4*6^(2n)-121 factors to (2*6^n-11)*(2^6^n+11) so all even n should be removed but since c>1 and c<-1 are not being considered that is not the case.

This will be a tremendous effort to get completely correct. I'm still not in favor of it. You seem to think that the code changes will be easy but they never are. Serge already found one bug, I have now found 3 bugs (1 previously and 2 now), and you found 3 more bugs. That's 7 bugs already and I'm just getting started on testing. When I look at all of the multiple srsieve version changes that were previously made for just removing squares it makes me cringe trying to do this. We have to comprehensively test this before an official version is posted.

[rogue]

Originally Posted by gd_barnes

Sounds like a lot of good testing.

Features on GFN's:

1. Do we really want to completely remove GFN's from sieving? Some people may want to sieve for them. I realize that srsieve is not the best siever for them but completely removing GFN's gives the impression that they are always composite, which is not the case. My suggestion is to remove your code for GFN's and let the program sieve them like it always has.

2. It did not write anything to algebraic.log about the removal of the GFN. Should it be doing that?

So far I've tried a lot of different powers including k's with multiple powers (such as k=2^30) and it looks good. I still have plenty of parallel testing to go.

It doesn't log GFNs because it doesn't find factors for them. I agree that I could eliminate that code and give a warning that GFNs are better sieved with gfnsieve (or whatever is available).

[rogue]

Originally Posted by gd_barnes

Some bugs:

1. It continues trying to sieve a sequence even if all terms have been removed and it doesn't seem to go very fast even though no terms remain. The same problem occurs for both algebraic factors and GFNs. When finished it just writes a file with the standard header line and nothing else. This could result in quite a bit of extra CPU time if the sieve depth is deep. Examples: 8*1000^n+1 or 10*1000^n+1.

2. It crashes every time I try to feed it an already sieved file. Old srsieve had no problem with this. I even tried random sieve files with no algebraic factors and it still crashed. We need to be able to feed it our existing sieve files and have it remove algebraic factors for us. Also for other projects such as repeat-digit sequences where c not = 1 or -1 neither sr1sieve nor sr2sieve can be used for additional sieving. Example sieve file: http://www.noprimeleftbehind.net/cru...-100K-400K.txt

Question:

If we're doing this, shouldn't we go all the way with it? I think that others have made that statement in this thread. Why are only c=1 and -1 being considered for algebraic factors? For example srsieve can easily sieve 4*6^n-121. 4*6^(2n)-121 factors to (2*6^n-11)*(2^6^n+11) so all even n should be removed but since c>1 and c<-1 are not being considered that is not the case.

For #1, it should stop if there are no terms remaining. I'll look into it.

I do not know how I introduced #2, because the changes are for new sequences only.

As to your last question, I hadn't considered supporting abs(c) != 1. Let me work out the other issues before I do that.