mtsieve

[ryanp]

With xyyxsievecl v2.2, with an input terms file of ~120K terms, I'm able to pull about:

  p=19700696761, 67.20K p/sec

on an A100. This is using -g 108 and without specifying -G or -W. Wondering if that's the best fine-tuning I can do...

[rogue]

The testing is looking good. No invalid factors for what I have tested. I have committed changes to sourceforge, but I have not made a build available yet. The new code is much easier for me to work with.

An example of the output for Sierpinski is:

(s) Sequence has algebraic factorization: 512*8^n+1 -> k = 2^9 and b = 2^3 and gcd(9,3) > 1

Riesel looks pretty much the same except for (r) instead of (s).

These are the first algebraic factor tests. None of the others are applied if either of these removes all terms for a sequence. That helps clean up the output a little.

To help with my testing I added a -a command line switch. When used srsieve2 will terminate immediately after checking for algebraic factors.

[gd_barnes]

All sounds great, Mark! I look forward to running the new version through my myriad of test cases and then some.

Clarification: You continue to use gcd > 1 when referencing the powers (i.e. f & g) for the removal of all n's on the Sierpinski side. That's not quite right. It would be correct for Riesel bases but it should be gcd > 2 for Sierpinski bases. Example:

k = x^6 and b = y^10, i.e. f = 6 and g = 10 per your previous examples.

x^6*(y^10)^n+1 would only have algebraic factors where n is divisible by 3 [since x^6 = (x^2)^3]. Since the gcd of (f,g) = (6,10) is only 2, all terms cannot be removed. That contradicts your gcd > 1 statement.

(Perhaps we are talking past each other again. )

Onto your latest example: It could more simply state:

(s) Sequence has algebraic factorization: 512*8^n+1 -> k = 8^3 and b = 2^3

That way, there's no need to reference gcd.

But if you left it the way you did, to be mathematically accurate you'd need to say gcd > 2 since it's a Sierpinski form.

Taking this a step further, when srsieve2 writes output to the screen of the nature you described, you could always state k and b in such a way that the powers are always equal. When the gcd is > 2 (> 1 for Riesel), that would always be the case. That way you could avoid mention of gcd altogether.

If you stated it that way, it would be easier to understand for the less-algebraically inclined people.

[henryzz]

To me, it feels logical for algebraic factorizations to be output to a file in a format such as:

9*2^(2*n)-1 = (3*2^n-1)*(3*2^n+1)
25*2^(2*n)-1 = (5*2^n-1)*(5*2^n+1)

If all the formulas are output like this it should be fairly easy to check that the factorizations make sense. It still wouldn't be 100% trivial for the number of ks that srbsieve ends up with at times for large conjectures but it is a good start.

The output rouge mentioned probably contains the needed information but it is rather obtuse.

[rogue]

All algebraic factors are written to a file that can then be input to pfgw to verify that factor.

srsieve2 generates output like this to the screen:

(r) Sequence has algebraic factorization: 125*1000^n-1 -> k = 5^3 and b = 10^3 and gcd(3,3) > 1
(r) Sequence 125*1000^n-1 has 100 terms removed due to algebraic factors of the form 5*10^n*-1

(s) Sequence has algebraic factorization: 125*1000^n+1 -> k = 5^3 and b = 10^3 and gcd(3,3) > 2
(s) Sequence 125*1000^n+1 has 100 terms removed due to algebraic factors of the form 5*10^n*+1

(cr) Sequence has algebraic factorization: 729*1002^n-1 -> 729*1002^6 = (3^6*2^3*167^3)^2
(cr) Sequence 729*1002^n-1 has 0 terms removed due to algebraic factors of the form (3^6*2^3*167^3)*1002^((n-6)/2)-1

(kp) Sequence has algebraic factorization: 841*1002^n-1 -> (29^2)*1002^n-1
(kp) Sequence 841*1002^n-1 has 50 terms removed due to algebraic factors of the form 29*1002^(n/2)-1

(b2) Removed 25 algebraic factors for 81*512^n+1 of the form (3^2)*2^(n/2)-3*2^((n+2)/4))+1 when n%4=2

(p4) Removed 100 algebraic factors for 4*81^n+1 of the form (2*(3^2)^n+2*(3^1)^n+1)

The algebraic factors follow the form that you see on that second line. (s) for Sierpinski also requires that gcd(x,y) != 2^n for some n > 0. It doesn't output that condition to the console. Note that I did change the text for the gcd to be > 2 for Sierpinski.

Regarding Gary's example it outputs this for Riesel:

(r) Sequence has algebraic factorization: 729*1024^n-1 -> k = 3^6 and b = 2^10 and gcd(6,10) > 1
(r) Sequence 729*1024^n-1 has 100 terms removed due to algebraic factors of the form 27*32^n*-1

and this for Sierpinski:

(kp) Sequence has algebraic factorization: 729*1024^n+1 -> (9^3)*1024^n+1
(kp) Sequence 729*1024^n+1 has 33 terms removed due to algebraic factors of the form 9*1024^(n/3)+1

[rogue]

I have released 2.5.1. Here are the changes:

twinsieve: version 1.6.3
   Fix issue when continuing a sieve from an input file.

xyyxsieve/xyyxsievecl: version 2.2
   Fix issue when using sparse terms where terms are not counted correctly.

srsieve2/srsieve2cl: version 1.7.3
   Refactored algebraic factorization code to avoid issues that plagued previous builds.

[pepi37]

MTSIEVE\TEST1>srsieve2.exe -P 1000000000 -n 500000 -N 1000000 -W 8 -l 5e9 -s"3*10^n+1" -s"4*10^n+1" -s"8*10^n+1" -s"9*10^n+1" -f B
srsieve2 v1.7.3, a program to find factors of k*b^n+c numbers for fixed b and variable k and n
(p4) Removed 125001 algebraic factors for 4*10^n+1 of the form (2*10^(n/2)+2*10^(n/4)+1)
(kp) Sequence has algebraic factorization: 8*10^n+1 -> (2^3)*10^n+1
(kp) Sequence 8*10^n+1 has 166667 terms removed due to algebraic factors of the form 2*10^(n/3)+1
Sieving with generic logic for p >= 3
Sieve started: 3 <= p <= 1e9 with 1708336 terms (500000 <= n <= 1000000, k*10^n+1) (expecting 1617771 factors)
Sequence 8*10^n+1 removed as all terms have a factor
Sieving with multi-sequence c=1 logic for p >= 257
BASE_MULTIPLE = 2, POWER_RESIDUE_LCM = 720, LIMIT_BASE = 720
Split 3 base 10 sequences into 108 base 10^60 sequences.
Legendre summary: Approximately 14 bytes needed for Legendre tables
3 total sequences
3 are eligible for Legendre tables
0 are not eligible for Legendre tables
2 have Legendre tables in memory
1 cannot have Legendre tables in memory
0 have Legendre tables loaded from files
2 required building of the Legendre tables

And just exit....

Without -l option works ok!

[rogue]

Originally Posted by pepi37

MTSIEVE\TEST1>srsieve2.exe -P 1000000000 -n 500000 -N 1000000 -W 8 -l 5e9 -s"3*10^n+1" -s"4*10^n+1" -s"8*10^n+1" -s"9*10^n+1" -f B
srsieve2 v1.7.3, a program to find factors of k*b^n+c numbers for fixed b and variable k and n
(p4) Removed 125001 algebraic factors for 4*10^n+1 of the form (2*10^(n/2)+2*10^(n/4)+1)
(kp) Sequence has algebraic factorization: 8*10^n+1 -> (2^3)*10^n+1
(kp) Sequence 8*10^n+1 has 166667 terms removed due to algebraic factors of the form 2*10^(n/3)+1
Sieving with generic logic for p >= 3
Sieve started: 3 <= p <= 1e9 with 1708336 terms (500000 <= n <= 1000000, k*10^n+1) (expecting 1617771 factors)
Sequence 8*10^n+1 removed as all terms have a factor
Sieving with multi-sequence c=1 logic for p >= 257
BASE_MULTIPLE = 2, POWER_RESIDUE_LCM = 720, LIMIT_BASE = 720
Split 3 base 10 sequences into 108 base 10^60 sequences.
Legendre summary: Approximately 14 bytes needed for Legendre tables
3 total sequences
3 are eligible for Legendre tables
0 are not eligible for Legendre tables
2 have Legendre tables in memory
1 cannot have Legendre tables in memory
0 have Legendre tables loaded from files
2 required building of the Legendre tables

And just exit....

I'll look into this.

[storm5510]

Originally Posted by pepi37

MTSIEVE\TEST1>srsieve2.exe -P 1000000000 -n 500000 -N 1000000 -W 8 -l 5e9 -s"3*10^n+1" -s"4*10^n+1" -s"8*10^n+1" -s"9*10^n+1" -f B
[B]srsieve2 v1.7.3], a program to find factors of k*b^n+c numbers for fixed b and variable k and n
(p4) Removed 125001 algebraic factors for 4*10^n+1 of the form (2*10^(n/2)+2*10^(n/4)+1)
(kp) Sequence has algebraic factorization: 8*10^n+1 -> (2^3)*10^n+1
(kp) Sequence 8*10^n+1 has 166667 terms removed due to algebraic factors of the form 2*10^(n/3)+1
Sieving with generic logic for p >= 3
Sieve started: 3 <= p <= 1e9 with 1708336 terms (500000 <= n <= 1000000, k*10^n+1) (expecting 1617771 factors)
Sequence 8*10^n+1 removed as all terms have a factor
Sieving with multi-sequence c=1 logic for p >= 257
BASE_MULTIPLE = 2, POWER_RESIDUE_LCM = 720, LIMIT_BASE = 720
Split 3 base 10 sequences into 108 base 10^60 sequences.
Legendre summary: Approximately 14 bytes needed for Legendre tables
3 total sequences
3 are eligible for Legendre tables
0 are not eligible for Legendre tables
2 have Legendre tables in memory
1 cannot have Legendre tables in memory
0 have Legendre tables loaded from files
2 required building of the Legendre tables

And just exit....

Without -l option works ok!

I have seen this before also. It happens when I do not allocate enough memory for the "building" of the tables. You have 5e9 in your command line. Increase it to 50e9. If it still fails, keep increasing it.

[gd_barnes]

Originally Posted by henryzz

The output rouge mentioned probably contains the needed information but it is rather obtuse.

I'm not sure obtuse is the word you're looking for there. I don't think it is being annoyingly insensitive or irritatingly slow to understand.

Perhaps it's used a little differently across the pond. :-)

I feel like obscure fits a bit better. It's maybe a bit obscure for a non-math person.

...anyway, off on my grammar rambling for the day.

[rebirther]

Originally Posted by pepi37

MTSIEVE\TEST1>srsieve2.exe -P 1000000000 -n 500000 -N 1000000 -W 8 -l 5e9 -s"3*10^n+1" -s"4*10^n+1" -s"8*10^n+1" -s"9*10^n+1" -f B

A small hint, you could put all sequences in an inputfile like remain.txt

srsieve2.exe -P 1000000000 -n 500000 -N 1000000 -W 8 -l 5e9 -sremain.txt -f B