Algebraic factors in sieve files

[rogue]

I see what you mean regarding these factors.

[gd_barnes]

Based on the update date for srsieve in your link, it appears that no changes have been made since Jan. 29th. Did you upload the changes that you recently made?

[rogue]

Originally Posted by gd_barnes

Based on the update date for srsieve in your link, it appears that no changes have been made since Jan. 29th. Did you upload the changes that you recently made?

No, I have not. I will make all of the changes you want (fixing bugs, etc), then post a new one.

BTW, I think I have your code changes made, but I need to re-run a number of tests.

[rogue]

Although all terms can be removed from 4*10000^n+1, only 25% can be removed from 40*10000^n+1. The code was only testing for the latter, not the former. Of course the former is really easy to test compared to the latter. I suspect that I tried to generalize the simple case and ended up only supporting the latter case.

[gd_barnes]

Originally Posted by rogue

Although all terms can be removed from 4*10000^n+1, only 25% can be removed from 40*10000^n+1. The code was only testing for the latter, not the former. Of course the former is really easy to test compared to the latter. I suspect that I tried to generalize the simple case and ended up only supporting the latter case.

40*10000^n+1 is not of the form 4*x^z*y^m+1 where z%4=0 and m%4=0. Here k=40 so x could not be an integer if z%4=0. If the code is checking for algebraic factors of this form, it is mistaken.

To the best of my knowledge, 40*10000^n+1 does not contain any algebraic factors. You stated that 25% of them can be removed. Can you explain?

I just ran it through the new srsieve and it removes no algebraic factors, which I believe is correct.

[gd_barnes]

Another crash bug, a display feature, and a writing to algebraic.log feature:

Crash bug:

Either 4*324^n-1 and 9*324^n-1 crash the program. This happens if they are sieved separately or if they are sieved together. For reference I used the command:
srsieve -G -P 10e6 -n 1 -N 100e3 -m 4e9 "9*324^n+1".

These forms fit your change log as follows:
Trivial -> where k*b^n-1 can be written as x^m-1

The same problem seems to occur for any sequence where k=x^2 and b=y^2. Oddly it does not seem to happen if k=x^3 and b=x^3.

This bug is different than those previously posted because it correctly runs through to completion, removes all algebraic factors as it should, and writes algebraic.log**(see below). But after doing so it crashes.

Because it crashes it doesn't write any sieve file. I feel like it is a good standard to not write a sieve file if no n's are remaining. The problem here is that it crashes.

Display feature:

The display on the command prompt screen is overly confusing and complex. For 9*324^n-1 it shows:

Removed 50000 algebraic factors for 9*324^n-1 as 324=18^2 and 9=3^2
Removed 50000 algebraic factors for 9*324^n-1 as 324=18^2 and 9*18^4=3^5*2^2^2

The first line is straight forward and looks good. The second seems overly complex and confusing to a person less familiar with how algebraic factors work.

I think it would be more understandable if the program simply stated:
Removed 100000 algebraic factors for 9*324^n-1 as 324=18^2 and 9=3^2

After all, all n's are removed for the simple reason that base and k are squares.


Writing to algebraic.log feature:

Algebraic.log has the same overly complex issue that the command prompt display has. In the case where k is a square and b is a square, ALL factors can just show:

(3*18^1-1) | 9*324^1-1
(3*18^2-1) | 9*324^2-1
(3*18^3-1) | 9*324^3-1
(3*18^4-1) | 9*324^4-1
(3*18^5-1) | 9*324^5-1
(3*18^6-1) | 9*324^6-1
(etc.)

Instead it shows:

(3*18^1-1) | 9*324^1-1
(3*18^3-1) | 9*324^3-1
(3*18^5-1) | 9*324^5-1
.
.
.
(3^5*2^2*18^0-1) | 9*324^2-1
(3^5*2^2*18^2-1) | 9*324^4-1
(3^5*2^2*18^4-1) | 9*324^6-1

Two points here:
1. All n's are removed because k is a square and b is a square. The display on the screen and the factors in algebraic.log need to be simplified.

2. I think this overly complex method of displaying and writing factors is causing quite a few of the bugs mentioned yesterday. This over complexity is more prevalent when all n's end up needing to be removed.

The complex display and writing of factors issue looks even more over-the-top complex for k=x^3 and b=x^3.


** If both are sieved together, it only writes the algebraic factors for 9*324^n-1. As discussed in a previous bug algebraic factors for k's < largest k are not written.

[gd_barnes]

Weird bug and a general command prompt screen display issue:

Weird bug:

8*324^n-1 causes the program to go into what appears to be an endless loop. It never stops. I have to stop it with Ctl-C. This is the first time I've encountered that.

I do not know why this happens. I thought it was related to the fact that k=x^3 and b=x^2 but I tried other similar forms like 27*324^n-1, 8*784^n-1, and 27*784^n-1. All seemed to work correctly.

General issue with command prompt screen display:

When k=x^q and b=x^r and q is coprime to r the display is misleading. Two cases:

For 27*324^n-1 it shows:
Removed 33333 factors for 27*324^n-1 as 324=18^2 and 27=3^3

For 9*216^n-1 it shows:
Removed 50000 factors for 9*216^n-1 as 216=6^3 and 9=3^2

These statements are misleading as follows:
1. In the first case it is removing the 33333 factors because 27=3^3 not because 324=18^2. 324 being a perfect square does not affect anything.

2. In the second case it is removing the 50000 factors because 9=3^2 not because 216=6^3. 216 being a perfect cube does not affect anything.

So they should show:
1. Removed 33333 factors for 27*324^n-1 as 27=3^3

2. Removed 50000 factors for 9*216^n-1 as 9=3^2

When it uses the word "as", it implies that both k and base are relevant in the algebraic factors being removed. That is not the case.

Note that what I believe they should show is what they DO show when the base is not a power.

Also note that BOTH base and k should be displayed when q is not coprime to r (most of the time they would be equal). That's because both base and k being a square or a cube would have an effect of removing all n.

I checked this with a base that contained a 5th power and the same issue exists so I believe it always exists where the k and base have different powers that are coprime to one another.

This is a nitpick but it goes towards a strict guideline that will help in resolving quite a few of the bugs that are being found. That is:

If the powers of both base and k are relevant, then both should be displayed on the screen and most frequently all n's will need to be removed. (Not always but quite often.) If only the k is relevant most often only part of the n's should be algebraically removed. So I think if you can get that display issue consistent it will go a long way towards getting all of the algebraic factors correctly removed. I also think it will help simplify the factors that are being written to algebraic.log.

[gd_barnes]

Some general bugs when k and base are both perfect cubes:

1. 27*64^n-1, 27*64^n+1, 125*64^n-1, 125*64^n+1, 8*729^n-1, and 8*729^n+1 should have all of their n's removed by algebraic factors. But srsieve is only removing n==(1 or 2) mod 3.

2. 8*64^n-1. 8*64^n+1, and 64*729^n-1 crash the program. In a previous bug I stated that when k and base are perfect squares it always crashes the program. This one is different. These are more unique cases.

3. 64*729^n+1 should have all of its n's removed by algebraic factors. But srsieve is removing n==(1 or 2) mod 3 -and- n==(0 mod 12) [ !! ] Therefore n==(3, 6, 9) mod 12 are remaining.

4. 729*512^n-1 should have all of its n's removed by algebraic factors. But srsieve is removing n==0 mod 2 -and - n==1 mod 6. Therefore n==(3 or 5) mod 6 are remaining.

5. 729*512^n+1 should have all of its n's removed by algebraic factors. But srsieve is removing only n==1 mod 3.

The problem seems to always occur when the k is a cube and the base is a 6th or 9th power. (I also confirmed that the problem exists for base=3^9=19683. So in the general sense when the form is k^3*b^6-+1 or k^3*b^9+-1 there is going to be some kind of bug. (Likely it exists for all bases where the power is > 3 and is a multiple of 3.) We just don't know what it will be.

All other forms that I tested where k and base are perfect cubes and where base is not a 6th/9th power seem to work correctly and remove all n's without crashing. I cannot guarantee that I tested all of them but I think this at least narrows the problem to when it occurs.

The most bizarre thing about the above is that 64*729^n-1 crashes the program whereas 64*729^n+1 has the bug of leaving just a teeny few n's after removing algebraic factors.

IMPORTANT NOTE: In a few of these cases, a trivial "numeric" factor ends up removing all of the terms but the bug still exists and would create a problem for a similar form that did not have a trivial factor. This may be the case on several of the bugs that I've posted. Do not be mislead by the fact that srsieve ends up removing trivial numeric factors after it missed some algebraic factors that it should have caught.

[gd_barnes]

This is not really another bug but it is a synopsis and analysis of one or more bugs previously posted:

If k and b are both squares the program crashes. (already posted)

If k and b are both cubes the program finds an overly complex set of algebraic factors. One each for n==(0, 1, and 2) mod 3. This causes it to frequently miss some of the algebraic factors. For k^3*(b^3)^n-1 just a simple factor of k*b^n-1 for all n is all that is needed both in the display and in algebraic.log. I am confused by the complexity that I am seeing.

If k and b are both 5th powers the problem is even more acute. 32*243^n-1 and 32*243^n+1 only remove n==(0 mod 5). 1024*243^n-1 and 1024*243^n+1 remove an even more confusing set of algebraic factors. That seems to be the case with several 5th powers that I tested. All n's should be removed by algebraic factors when both k and base have the same power (Sierp >= 3). Once again for all k^5*(b^5)^n-1 a simple factor of k*b^n-1 is all that is needed.

Note that all of these fit this form in your change log:
Trivial -> where k*b^n-1 can be written as x^m-1

So they all need a serious look.

I will stop testing now for a few days and allow you to catch up. I have made an effort to separate each bug into a unique case but it is possible that a single code fix may resolve 2 or 3 of them. I have to pile on when I'm in town because when I leave in a couple of weeks I will have little time.

For reference I am testing this on a ~5-year-old Intel I7 920 running at 2.67 Ghz with 4 GB of RAM. It is 64 bit and I am running Windows 7. It's an older but very effective machine. :-)

[rogue]

Originally Posted by gd_barnes

I will stop testing now for a few days and allow you to catch up. I have made an effort to separate each bug into a unique case but it is possible that a single code fix may resolve 2 or 3 of them. I have to pile on when I'm in town because when I leave in a couple of weeks I will have little time.

Thanks. I need to catch my breath too.

I really do appreciate your efforts even though you have been rather hard on me.

[gd_barnes]

I think a large part of the problem is the project definition. Here is a complete project definition of what I think is needed:

General:

1. If k*b^n-1 can be written as 2^y-1; display a warning message on the screen that the form is a mersenne number and could better be factored or sieved with another program.

2. If k*b^n+1 can be written as x^y+1; and x, y > 1; display a warning message on the screen that the form is a GFN and could better be sieved with another program.

Remove all n cases:

1. If form is k^x*(b^y)^n-1; and x, y >= 2; and x, y == (0 mod 2); remove all n.

2. If form is k^x*(b^y)^n-1 or k^x*(b^y)^n+1; and x, y > 2; and [ x == (1 mod 2) -or- y == (1 mod 2) ]; and GCD of x, y > 1; remove all n.

Note that the -or- part here is important especially in a previously posted problematic case where x=3 and y=6. Only x meets the condition but that is sufficient. Here GCD of x, y = 3 so both are perfect cubes and should have all n's removed. In effect the -or- statement is a negation of the requirement from #1 where x, y == (0 mod 2).

3. If form is 4*k^x*(b^y)^n+1; and x, y == (0 mod 4); remove all n. These are Aurelian (spell) factors.

The above should all be checked first before preceding.

Remove partial n cases:

1. If form is k^x*(b^y)^n-1; and x==(0 mod 2); and GCD x, y = 1; remove all n == (0 mod 2).

2. If form is k^x*(b^y)^n-1 or k^x*(b^y)^n+1; and x > 2; and x==(1 mod 2) and GCD x, y = 1; let f(x) = the prime factors of x. For each f(x), remove all n == [ 0 mod f(x) ].

It is somewhat unlikely to have a k with more than one odd power > 2. The smallest example would be k=32768, which is 2^15. But we have such huge k's at CRUS that we have to go all the way with this. Hence all of the powers of the k must be determined and all of their algebraic factors removed. For k=32768 all n==(0 mod 3) and n==(0 mod 5) would be removed. Note: Srsieve already handles this correctly.

3. If form is 4*k^x*(b^y)^n+1; and x == (0 mod 4); and y not == (0 mod 4), remove all n == (0 mod 4).

4. If form is k^x*(2^y)^n+1; and x == (0 mod 4); and y == (2 mod 4); remove all n == (1 mod 4).

5. If form is k^x*(2^y)^n+1; and x == (0 mod 4); and y == (1 mod 2); remove all n == (2 mod 4).

#3, 4, and 5 are more Aurelian factors.

Coordination with existing code:

1. If all n's are removed by algebraic factors for all k, program should stop immediately.

2. If some n's are removed by algebraic factors, program continues sieving for numeric factors.

3. Program should be able to handle input of one or multiple k's for a new base at the screen or in a file. Some k's could have algebraic factors while others do not. This could include BOTH Riesel and Sierp k's for the same base in the same file.

4. Program should be able to handle an already sieved file as input, check the file for algebraic factors, remove them, and then continue sieving more deeply. Once again some k's could have algebraic factors while others do not and there could be both Riesel and Sierp k's in the file for the same base.

Note that the requirement for being able to handle both Riesel and Sierp k's in the same file is important. Usually a -G or -g format file is fed into srsieve but it can also handle the -a or -w format as input, which could include k's on both sides.

Note that the above is complex. I've tried to cover all of the cases but it is possible that there may be a logic error in there. Any input is welcome from anyone. Mark, I suspect that it may be easier for you to strip out all current algebraic factors code and start from scratch with this project definition. I think it will result in a lot less work than trying to make the current code fit this definition.

Good luck!