mersenneforum.org Algebraic factors in sieve files
 Register FAQ Search Today's Posts Mark Forums Read

2017-01-31, 23:28   #45
gd_barnes

May 2007
Kansas; USA

25·317 Posts

Quote:
 Originally Posted by rogue 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).
I think that would be better to just give a warning message for GFNs. I feel like it would not be good to give the impression that GFNs cannot possibly contain primes.

Quote:
 Originally Posted by rogue As to your last question, I hadn't considered supporting abs(c) != 1. Let me work out the other issues before I do that.
I agree that c=1 or -1 (with no changes for c != 1 and -1) should be done as one main version...fully tested and implemented...since that is where the bulk of sieving occurs. There's no use to introduce any additional risk into the bulk of sieving efforts at this point. Then if you decide to take on c != 1 and -1 then that should be a completely new version...once again tested in a similar manner before implementation.

Last fiddled with by gd_barnes on 2017-02-01 at 00:11

 2017-02-01, 02:02 #46 gd_barnes     May 2007 Kansas; USA 25×317 Posts Another bug that I believe is a symptom of the #2 bug that I posted previously: If you feed a k's remaining file (instead of a sieve file) to the new srsieve, it won't crash but it gives this error message: "Unrecognised sequence or file 'remain-S1002.txt'" The file works just fine with old srsieve. File remain-S1002.txt contains: Code: 152*1002^n+1 492*1002^n+1 613*1002^n+1 707*1002^n+1 917*1002^n+1 The command that I gave it at the command prompt was: srsieve -G -P 10e6 -n 1 -N 1e6 -m 4e9 -zz remain-S1002.txt Note that if the sequences are specified at the command prompt it works just fine, i.e.: srsieve -G -P 10e6 -n 1 -N 1e6 -m 4e9 -zz "152*1002^n+1" "492*1002^n+1" "613*1002^n+1" "707*1002^n+1" "917*1002^n+1" works great. It appears that you only tested using sequences specified at the command prompt. Any kind of file inputs either crash the program or result in an error message. Last fiddled with by gd_barnes on 2017-02-01 at 02:14
 2017-02-01, 02:33 #47 gd_barnes     May 2007 Kansas; USA 25·317 Posts Another bug: When more than one sequence is sieved, it will only write algebraic factors to algebraic.log for the largest k regardless of the order that the sequences are specified. Any k less than the largest k will not have its algebraic factors written. This happens regardless of whether the k's < largest k have algebraic factors or not. Multiple tests confirmed this. Note that the factors are correctly removed from the ultimate sieve file. Only algebraic.log is incorrect. Examples: 1. One smaller algebraic k and one larger non-algebraic k: srsieve -G -P 10e6 -n 1 -N 1e6 -m 4e9 -zz "8*1002^n+1" "152*1002^n+1" -and- srsieve -G -P 10e6 -n 1 -N 1e6 -m 4e9 -zz "152*1002^n+1" "8*1002^n+1" will not write algebraic factors to algebraic.log for k=8. 2. Two algebraic k's: srsieve -G -P 10e6 -n 1 -N 1e6 -m 4e9 -zz "8*1002^n+1" "27*1002^n+1" -and- srsieve -G -P 10e6 -n 1 -N 1e6 -m 4e9 -zz "27*1002^n+1" "8*1002^n+1" Will only have algebraic factors written to algebraic.log for k=27. k=8 is not written. 3. One smaller non-algebraic k and one larger algebraic k: srsieve -G -P 10e6 -n 1 -N 1e6 -m 4e9 -zz "152*1002^n+1" "512*1002^n+1" -and- srsieve -G -P 10e6 -n 1 -N 1e6 -m 4e9 -zz "512*1002^n+1" "152*1002^n+1" Will correctly have its algebraic factors written to algebraic.log for k=512. This conclusively shows that the bug exists for all algebraic k's < the largest k. It isn't a problem when only one algebraic sequence is sieved because that one k is the largest k. :-) Last fiddled with by gd_barnes on 2017-02-01 at 03:02
 2017-02-01, 03:16 #48 gd_barnes     May 2007 Kansas; USA 25×317 Posts Feature: Algebraic.log should not be written at all if there are no algebraic factors, even as an empty file. Not writing it would make it consistent with sr2sieve that does not write a factors.txt file if there are no factors. Last fiddled with by gd_barnes on 2017-02-01 at 03:23
 2017-02-01, 04:59 #49 gd_barnes     May 2007 Kansas; USA 1014410 Posts A major bug: Where k=p^q, if the lower bound of n is greater than q -AND- n is NOT a multiple of q, the program crashes. (Of course only q>=3 for Sierp sequences.) If multiple k's are being sieved just a single k with algebraic factors among the bunch will crash it. It took multiple tests to confirm the specific lower bounds of n's that caused the crash. I think it has to do with the algebraic factors routine wanting to start from a multiple of q. It can start correctly if n<=q but if n>q then n must be a multiple of q for the program to run correctly. This is a blatant and very strange problem that would affect likely 90%+ of all sieves that we do here if at least one of the k's has algebraic factors since we rarely sieve at such low n-ranges. I should have caught it the very first thing. But all of my tests were with a lower bound of n=1. It seems to not crash if the lower bound is n<=q except in the case of file inputs as previously stated. Examples: 1. srsieve -G -P 10e6 -n 4 -N 1e6 -m 4e9 -z "8*86^n+1" Here 8=2^3 so q=3 hence a lower bound of n=4, which is not a multiple of 3, crashes the program. A lower bound of n<=3 or n=6 or n=9 does not crash the program. It runs through correctly to completion. 2. srsieve -G -P 10e6 -n 6 -N 1e6 -m 4e9 -z "243*86^n+1" Here 243=3^5 so q=5 hence a lower bound of n=6, which is not a multiple of 5, crashes the program. A lower bound of n<=5 or n=10 or n=15 does not crash the program. It runs through correctly to completion. 3. srsieve -G -P 10e6 -n 3 -N 1e6 -m 4e9 -z "4*86^n-1" Here 4=2^2 so q=2 hence a lower bound of n=3, which is not a multiple of 2, crashes the program. A lower bound of n<=2 or n=4 or n=6 does not crash the program. It runs through correctly to completion. Most strange example is where k has multiple q's such as in 64*87^n-1. Since 64=8^2 or 4^3, q can be either 2 or 3. If the lower bound of n>2, then that lower bound must be a multiple of 2*3=6 for the program to run correctly! Very bizarre! I have not even gotten to doing any testing of forms where k*b^n+1 can be written as 4*x^z*y^m+1. That should be fun. I also have only done limited parallel testing. Plenty more to go. Last fiddled with by gd_barnes on 2017-02-01 at 06:02
 2017-02-01, 06:37 #50 gd_barnes     May 2007 Kansas; USA 25×317 Posts Another bug: I ran my first test for k*b^n+1 that can be written as 4*x^z*y^m+1 where z%4=0 and m%4=0. It did not turn out too well. I started with our lowest-base example of 2500*16^n+1, which has been proven to have algebraic factors for all n. So srsieve should remove all n but it did not. There is also a factor display issue on the screen that I discuss further below **. The example that I use on the CRUS web page is: For all n: let k=4*q^4 and let m=q*2^n; factors to: (2*m^2 + 2m + 1) * (2*m^2 - 2m + 1) I ran this through srsieve with: srsieve -G -P 1e9 -n 1 -N 100e3 -m 4e9 -z "2500*16^n+1" Some srsieve output: Removed 25000 algebraic factors for 2500*16^n+1 of the form (5^2)*2^(n/2)-5*2^((n+2)/4))+1 when n%4=2 Removed 25000 algebraic factors for 2500*16^n+1 of the form (2*2500^2)*16^(n/2)-2*2500*16^(n/4)+1 when n%4=0 So it is not removing all n. Obviously by this it appears that srsieve is removing all n==(0 or 2) mod 4. But that is not the case. When I looked in algebraic.log here are the first few lines of each set of algebraic factors in the log that it showed as having been removed: Code: (5^2*2^3-5*2^2+1) | 2500*16^1+1 (5^2*2^11-5*2^6+1) | 2500*16^5+1 (5^2*2^19-5*2^10+1) | 2500*16^9+1 (5^2*2^27-5*2^14+1) | 2500*16^13+1 (5^2*2^35-5*2^18+1) | 2500*16^17+1 . . . ((2*5^2)*16^2-2*5*16^1+1) | 2500*16^4+1 ((2*5^2)*16^4-2*5*16^2+1) | 2500*16^8+1 ((2*5^2)*16^6-2*5*16^3+1) | 2500*16^12+1 ((2*5^2)*16^8-2*5*16^4+1) | 2500*16^16+1 ((2*5^2)*16^10-2*5*16^5+1) | 2500*16^20+1 So...in algebraic.log it states that it is removing all n==(0 or 1) mod 4 whereas the display shows that all n==(0 or 2) mod 4 are being removed. So which is it? Both are incorrect. ALL n should be removed. With algebraics removing all n==(0 or 1) mod 4 and a factor of 17 removing all n==3 mod 4, there were many terms remaining in the final sieve file that were all n==2 mod 4. The first few lines of the sieve file are: Code: 1000000000:P:1:16:257 2500 306 2500 678 2500 894 2500 966 2500 974 Interestingly srsieve removes all terms for 40000*16^n+1 (k=2500*16) but that's only because it got lucky due to the fact that a factor of 17 removed all n's that weren't found with algebraic factors...when in fact ALL n's should have been removed by algebraic factors. ** There is also a display issue of the factors on the command prompt screen. For this form, the factorization of ALL n should be: [5^2*2^(2n+1)-5*2^(n+1)+1] * [5^2*2^(2n+1)+5*2^(n+1)+1] That is the entire factorization of all n. Using the usual format of displaying only the smallest factor, srsieve should be displaying something like the following on the screen: Removed 100000 algebraic factors for 2500*16^n+1 of the form 5^2*2^(2n+1)-5*2^(n+1)+1 The n in the factors should be greater than the n for 2500*16^n+1 because it is reducing k=2500 to 5^2 and base=16 to 2^x meaning that the exponents in the factors have to be greater to account for the reduced k and base. They should be (2n+1) and (n+1) not...(n/2) and ((n+2)/4). Even if the factors in algebraic.log were correct their general form is being incorrectly displayed on the screen. Example for n=10 using the factordb: 2500*16^10+1 = 13^2 * 41 * 310169 * 1279001 Using the factor displayed on the screen of (5^2)*2^(n/2)-5*2^((n+2)/4))+1: Since n/2 = 5 and (n+2)/4 = 3, you would have 5^2*2^5 - 5*2^3 + 1 = 761...not a factor of 2500*16^n+1 Correct is 5^2*2^(2n+1)-5*2^(n+1)+1: Since 2n+1 = 21 and n+1 = 11, you would have 5^2*2^21-5*2^11+1 = 52418561 = 13^2 * 310169, which are part of the factors of 2500*16^n+1. Edit: Even more bizarre...if I set the lower bound to n==2 mod 4, it removes all terms from 2500*16^n+1 because of the removal of the factor of 17. Otherwise it does not remove all terms. But this is still incorrect. It should remove all terms with algebraic factors and not even go into the usual sieving routine for "numeric" factors. So...there is something going on with the lower bound of n that is either crashing the program or causing it to miss different sets of algebraic factors. Last fiddled with by gd_barnes on 2017-02-01 at 08:54 Reason: edit
 2017-02-01, 08:45 #51 gd_barnes     May 2007 Kansas; USA 25×317 Posts Another bug: I ran another test for k*b^n+1 that can be written as 4*x^z*y^m+1 where z%4=0 and m%4=0. This time I chose the smallest k that could fit the form, k=4. Unfortunately the smallest bases that this could be tested on are b=5^4 and 10^4 because all other bases where 4*b^4+1 have trivial factors of 5 for all n. So I tried 4*625^n+1 and 4*10000^n+1. It did not remove any n's at all with algebraic factors but it should have removed all of them. So this is a different bug than the last one. I'm not done yet but I am done for the night. Last fiddled with by gd_barnes on 2017-02-01 at 08:55
 2017-02-01, 14:26 #52 rogue     "Mark" Apr 2003 Between here and the 578310 Posts Thanks for being so thorough Gary. I did fix the one issue with continuing from a previous file. It was due to some experimental code that I wrote a long time ago to address a different bug. It is not a problem in 1.0.8, but I was playing with it shortly after that release. I reverted that code back to 1.0.8. I agree that the sequences from a file is related to this. I also fixed the n > 1 issue. As soon as I have time, I will look at the other issues you have listed. Last fiddled with by rogue on 2017-02-01 at 14:46
2017-02-01, 15:20   #53
rogue

"Mark"
Apr 2003
Between here and the

132278 Posts

Quote:
 Originally Posted by gd_barnes Another bug: I ran another test for k*b^n+1 that can be written as 4*x^z*y^m+1 where z%4=0 and m%4=0. This time I chose the smallest k that could fit the form, k=4. Unfortunately the smallest bases that this could be tested on are b=5^4 and 10^4 because all other bases where 4*b^4+1 have trivial factors of 5 for all n. So I tried 4*625^n+1 and 4*10000^n+1. It did not remove any n's at all with algebraic factors but it should have removed all of them. So this is a different bug than the last one. I'm not done yet but I am done for the night.
I wouldn't call this a bug as much as the code isn't looking for this form. There are many that it checks for and many that it doesn't . This shouldn't be too hard to check for. Is there a more generic way to write this one?

Last fiddled with by rogue on 2017-02-01 at 15:22

2017-02-01, 20:32   #54
gd_barnes

May 2007
Kansas; USA

27A016 Posts

Quote:
 Originally Posted by rogue I wouldn't call this a bug as much as the code isn't looking for this form. There are many that it checks for and many that it doesn't . This shouldn't be too hard to check for. Is there a more generic way to write this one?
Yes it is a bug. 4*625^n+1 and 4*10000^n+1 are the same form as 2500*16^n+1, which also should have all of its n's removed by algebraic factors. But it is a different bug than 2500*16^n+1 because the former two find no algebraic factors and the latter one finds partial algebraic factors. They should all find full algebraic factors and have no n remaining. Also the output results for the latter form are different depending on the lower bound of n...perhaps that's been fixed now. I'll look at it in a little while.

All of these are of the generic forum:

4*x^z*y^m+1 where z%4=0 and m%4=0

This is the form specified in your "CHANGES" file. The changes imply that all of the algebraic factors should be found for the above generic form, which is not the case.

For 4*625^n+1, x=1, z=4, y=5, m=4

For 4*10000^n+1, x=1, z=4, y=10, m=4

For 2500*16^n+1, x=5, z=4, y=2, m=4

In other words, all of the same form.

My guess is that you are not checking for x=1, which is why k=4 removes nothing.

Quote:
 Originally Posted by rogue ...Adding these missing forms (or others) should be very easy to do.
At 10+ bugs and counting, are you still sticking with that statement?

Last fiddled with by gd_barnes on 2017-02-01 at 20:53

2017-02-01, 20:47   #55
gd_barnes

May 2007
Kansas; USA

100111101000002 Posts

Quote:
 Originally Posted by rogue Thanks for being so thorough Gary. I did fix the one issue with continuing from a previous file. It was due to some experimental code that I wrote a long time ago to address a different bug. It is not a problem in 1.0.8, but I was playing with it shortly after that release. I reverted that code back to 1.0.8. I agree that the sequences from a file is related to this.
Oh goodie. So for this experimental code that was supposed to address a different bug but was never actually implemented, can we presume that the "different bug" still exists because the experimental code has been removed?

Last fiddled with by gd_barnes on 2017-02-01 at 20:51

 Similar Threads Thread Thread Starter Forum Replies Last Post pinhodecarlos Riesel Prime Search 89 2020-04-04 17:00 gd_barnes Conjectures 'R Us 31 2010-04-06 02:04 davieddy Math 48 2009-07-07 19:42 mdettweiler Software 16 2009-03-08 02:06 henryzz ElevenSmooth 13 2007-12-18 09:12

All times are UTC. The time now is 14:34.

Fri Jul 3 14:34:35 UTC 2020 up 100 days, 12:07, 1 user, load averages: 2.17, 2.03, 1.94