mtsieve

[rogue]

Originally Posted by gd_barnes

Srsieve2 1.7.2 fails on algebraic factor removal similar to how versions 1.7.0 and prior did.

It is removing algebraic factors that it should not be when the k and base are different perfect powers. Therefore primes could be subsequently missed.

This was fixed in version 1.7.1 at the expense of having it not remove some algebraic factors that it should. Unfortunately it is now removing more than it should.

Examples:

9*8^n-1: It removes all terms. It should only remove terms divisible by 2.
27*32^n-1: It removes all terms. It should only remove terms divisible by 3.
32*125^n-1: It removes all terms. It should only remove terms divisible by 5.

As best as I can tell, this is only happening on the Riesel side at this time.

On the Sierpinski side, it is still missing some algebraic factors but that would have no affect on future primes found.

For anyone using 1.7.2 for the extra speed because it is no longer missing factors when using the Legendre tables, you should be OK if your base is not a power. Storm and Pepi, this means you will be OK. Your bases 78 and 773 are not powers so this error will not affect them.

I changed the code to address the case where it is "removing all terms", but it will still miss algebraic factors. In order for me to address that I would need examples of algebraic factors that are missed. Note that I am only focused on c = +1 and -1 sequences where d = 1. Algebraic factors for other c and d are not covered.

[k0r3]

Originally Posted by rogue

Problem found and fixed in sourceforge

Thanks for the quick fix. It still seems to have some issues with Newpgen format though.

.\twinsieve.exe -i newpgen.txt -o out2.txt
twinsieve v1.6.3, a program to find factors of k*b^n+1/-1 numbers for fixed b and n and variable k
Sieve started: 9650251852537 <= p <= 2^62 with 465320 terms

It dies right after that, here is the first lines of the file I'm trying

9650251852537:T:0:2:3
1293 333330

[rogue]

Originally Posted by k0r3

Thanks for the quick fix. It still seems to have some issues with Newpgen format though.

Fixed now

[k0r3]

Originally Posted by rogue

Fixed now

Seems to be working now, thanks!

[gd_barnes]

Originally Posted by rogue

I changed the code to address the case where it is "removing all terms", but it will still miss algebraic factors. In order for me to address that I would need examples of algebraic factors that are missed. Note that I am only focused on c = +1 and -1 sequences where d = 1. Algebraic factors for other c and d are not covered.

On Sierpinski bases where both k and base are equal powers >= 3, it is only removing n's divisible by the power of the k. It should remove all n's.

Below are some test cases. It should have removed all terms on these:

343*8^n+1 only removed terms divisible by 3.
125*216^n+1 only removed terms divisible by 3.
243*32^n+1 only removed terms divisible by 5.
3125*1024^n+1 only removed terms divisible by 5.

This is for version 1.7.2 from the last update of mtsieve a few days ago.

I did not see a new executable at SourceForge for your latest fix. I only saw where the source for AlgebraicFactorHelper.cpp had been changed earlier today. Maybe I'm missing something.

[rogue]

Originally Posted by gd_barnes

On Sierpinski bases where both k and base are equal powers >= 3, it is only removing n's divisible by the power of the k. It should remove all n's.

Below are some test cases. It should have removed all terms on these:

343*8^n+1 only removed terms divisible by 3.
125*216^n+1 only removed terms divisible by 3.
243*32^n+1 only removed terms divisible by 5.
3125*1024^n+1 only removed terms divisible by 5.

This is for version 1.7.2 from the last update of mtsieve a few days ago.

I did not see a new executable at SourceForge for your latest fix. I only saw where the source for AlgebraicFactorHelper.cpp had been changed earlier today. Maybe I'm missing something.

I have not posted it yet.

In short if we have k*b^n+1 where k = x^g and b = y^g and g is odd, then all terms would be GFN as they could be written as (x*y)^(g*n)+1. This is what I need to do to derive algebraic factorizations.

[gd_barnes]

Originally Posted by rogue

I have not posted it yet.

In short if we have k*b^n+1 where k = x^g and b = y^g and g is odd, then all terms would be GFN as they could be written as (x*y)^(g*n)+1. This is what I need to do to derive algebraic factorizations.

Coding specifically for g is odd wouldn't work. There's always powers of 6, 10, 12, etc. Those would reduce to a cube, 5th power, and cube respectively where all terms should be removed.

More specifically, all terms should be removed if:
g has an odd prime factor where itself counts as a prime factor

Stated in a different way, all terms should be removed if:
g is not a power of 2

Maybe you were getting at this but I wasn't clear on it.

[rogue]

I misstated. Hopefully this is correct. If k = x^f and b = y^g and gcd(f,g) > 1 then k*b^n+1 can only be prime if k*b^n+1 is a GFN. srsieve2 is not intended for sieving GFNs.

[gd_barnes]

Originally Posted by rogue

I misstated. Hopefully this is correct. If k = x^f and b = y^g and gcd(f,g) > 1 then k*b^n+1 can only be prime if k*b^n+1 is a GFN. srsieve2 is not intended for sieving GFNs.

Although that makes sense I'm unclear how we got off on the topic of GFNs and how it pertains to the original problem. If as you state k = x^f and b = y^g and gcd (f,g) > 1 make a GFN, I would add additional qualifications that must be there in order to remove all n-values, which is where we were going with it.

Specifically on the Sierpinski side, all n-values should be removed if:

( f = g and f,g >= 3 -and- f,g are not a power-of-2 )
-or-
( f,g >= 3 and gcd(f,g) >= 3 )

This expands on what I stated earlier, which wasn't inclusive enough. I had stated that the powers (f & g) had to be equal. But that's not enough. They can be unequal if they have a gcd >= 3.

I hope that covers all of the cases of the form x^f*(y^g)^n+1 where all n-values should be removed. But I wouldn't be surprised if there's something more out there.

[rogue]

It is my mistake if we are talking past one another. This algebraic factor stuff can be quite confusing.

If k = x^f and b = y^g and x = y and c = +1, then it is GFN. This is already handled.

Regarding your case I need to identify the divisors and dump them to the alg.txt file so they can be independently verified by pfgw (to ensure no coding errors in srsieve2.

This is not handled:
If k = x^f and b = y^g and gcd(x,y) > 2 and gcd(x,y) != 2^n for any n > 0 and c = +1, then each term has the factor of x*y+1.

These are handled:
If k = x^f and c = +1 and f is odd then each term where n%f = 0 has the factor x*b^(n/f)+1.
If k = x^f and c = -1 then each term where n%f = 0 has the factor x*b^(n/f)-1.

k = x^f and b = y^g and gcd(x,y) > 2 and c = -1 is handled incorrectly in the current release causing it to remove all terms but output a divisor that is equal to the term itself. This is how it should be handled:
If k = x^f and b = y^g and gcd(x,y) > 2 and c = -1, then each term has the factor of x*y^n-1.

[rogue]

Originally Posted by rogue

If k = x^f and b = y^g and gcd(x,y) > 2 and c = -1, then each term has the factor of x*y^n-1.

Not quite. if gcd(x,y) = m then x^(f/m)*y^(g/m)^n-1 is a factor.

For example for 64*36^n-1 we have factors of the form 8*6^n-1

I am in the process of testing to verify that no invalid factors are found for all b <= 1001 and all k <=1001 for a small range of n. Testing higher b and k will have to be done on a case-by-case basis.