20170131, 23:28  #45  
May 2007
Kansas; USA
2^{5}·317 Posts 
Quote:
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 20170201 at 00:11 

20170201, 02:02  #46 
May 2007
Kansas; USA
2^{5}×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 'remainS1002.txt'" The file works just fine with old srsieve. File remainS1002.txt contains: Code:
152*1002^n+1 492*1002^n+1 613*1002^n+1 707*1002^n+1 917*1002^n+1 srsieve G P 10e6 n 1 N 1e6 m 4e9 zz remainS1002.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 20170201 at 02:14 
20170201, 02:33  #47 
May 2007
Kansas; USA
2^{5}·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 nonalgebraic 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 nonalgebraic 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 20170201 at 03:02 
20170201, 03:16  #48 
May 2007
Kansas; USA
2^{5}×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 20170201 at 03:23 
20170201, 04:59  #49 
May 2007
Kansas; USA
10144_{10} 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 nranges. 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^n1" 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^n1. 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 20170201 at 06:02 
20170201, 06:37  #50 
May 2007
Kansas; USA
2^{5}×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 lowestbase 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^35*2^2+1)  2500*16^1+1 (5^2*2^115*2^6+1)  2500*16^5+1 (5^2*2^195*2^10+1)  2500*16^9+1 (5^2*2^275*2^14+1)  2500*16^13+1 (5^2*2^355*2^18+1)  2500*16^17+1 . . . ((2*5^2)*16^22*5*16^1+1)  2500*16^4+1 ((2*5^2)*16^42*5*16^2+1)  2500*16^8+1 ((2*5^2)*16^62*5*16^3+1)  2500*16^12+1 ((2*5^2)*16^82*5*16^4+1)  2500*16^16+1 ((2*5^2)*16^102*5*16^5+1)  2500*16^20+1 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 ** 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^215*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 20170201 at 08:54 Reason: edit 
20170201, 08:45  #51 
May 2007
Kansas; USA
2^{5}×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 20170201 at 08:55 
20170201, 14:26  #52 
"Mark"
Apr 2003
Between here and the
5783_{10} 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 20170201 at 14:46 
20170201, 15:20  #53  
"Mark"
Apr 2003
Between here and the
13227_{8} Posts 
Quote:
Last fiddled with by rogue on 20170201 at 15:22 

20170201, 20:32  #54  
May 2007
Kansas; USA
27A0_{16} Posts 
Quote:
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. At 10+ bugs and counting, are you still sticking with that statement? Last fiddled with by gd_barnes on 20170201 at 20:53 

20170201, 20:47  #55  
May 2007
Kansas; USA
10011110100000_{2} Posts 
Quote:
Last fiddled with by gd_barnes on 20170201 at 20:51 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
RSP Sieve Files for k*2^n1 from PrimeGrid  pinhodecarlos  Riesel Prime Search  89  20200404 17:00 
Generalizing algebraic factors on Riesel bases  gd_barnes  Conjectures 'R Us  31  20100406 02:04 
Constructing a sieve for trial factors  davieddy  Math  48  20090707 19:42 
program to verify factors found by sr(x)sieve?  mdettweiler  Software  16  20090308 02:06 
Algebraic factors  henryzz  ElevenSmooth  13  20071218 09:12 