mtsieve

[rogue]

Originally Posted by SethTro

Did this issue ever get fixed? I think I'm running into it again (but possible a different issue)

$ ./srsieve2 -W1 -p 10 -P 1e8 -n 10 -N 300000 -s "1*9^n-7"
srsieve2 v1.6.4, a program to find factors of k*b^n+c numbers for fixed b and variable k and n
Sieving with generic logic for p >= 10
Sieve started: 10 < p < 1e8 with 299991 terms (10 < n < 300000, k*9^n-7) (expecting 262492 factors)
Sieving with single sequence c=1 logic for p >= 257
BASE_MULTIPLE = 30, POWER_RESIDUE_LCM = 720, LIMIT_BASE = 720
Split 1 base 9 sequence into 132 base 9^180 sequences.
Legendre summary:  Approximately 2 B needed for Legendre tables

...

518400 bytes used for congruent q and ladder indices
263200 bytes used for congruent qs and ladders
Fatal Error:  Invalid factor: 1*9^39060-7 mod 1303 = 1297

I'm sieving "(3^n-7)/2" which I think I can hack to avoid d by testing 9^n-7 and disabling the division by 2 test. I'm excited that srsieve2 might be 10-100x faster than my hand coded sieve.

Sorry, but I have not. I am mainly stuck on how to handle terms that are not divisible by the divisor. For example if you had (3^n-1)/5, then how do I handle terms where 3^n-1 is not already divisible by 5. I think that pfgw actually tests floor((3^n-1)/5). The challenge is two-fold. Just because p divides 3^n-1 for some value of n, it doesn't mean that p divides floor(3^n-1)/5 for that same value of n. The converse is also true. p could divide floor(3^n-1)/5, but does not divide 3^n-1. The algorithm behind srsieve2 works by finding factors of 3^n-1 so it cannot find some of the factors that would divide floor((3^n-1)/5).

Given the values you have for k, b, c, and d, 3^n-7 is always even, so always divisible by 2. I could make a change to support sieving sequences meeting these criteria:

• d is prime
• d evenly divides all k*b^n+c terms

I would then need to:

• Remove all terms where k*b^n+c is divisible by d^2
• Skip the discrete log where d = p.

That would mean that all factors found by the discrete log divide both k*b^n+c and (k*b^n+c)/d.

I don't know when I can complete this, but it is the best I can offer at this time.

[SethTro]

Originally Posted by rogue

Sorry, but I have not. I am mainly stuck on how to handle terms that are not divisible by the divisor. For example if you had (3^n-1)/5, then how do I handle terms where 3^n-1 is not already divisible by 5. I think that pfgw actually tests floor((3^n-1)/5). The challenge is two-fold. Just because p divides 3^n-1 for some value of n, it doesn't mean that p divides floor(3^n-1)/5 for that same value of n. The converse is also true. p could divide floor(3^n-1)/5, but does not divide 3^n-1. The algorithm behind srsieve2 works by finding factors of 3^n-1 so it cannot find some of the factors that would divide floor((3^n-1)/5).

Given the values you have for k, b, c, and d, 3^n-7 is always even, so always divisible by 2. I could make a change to support sieving sequences meeting these criteria:

• d is prime
• d evenly divides all k*b^n+c terms

I would then need to:

• Remove all terms where k*b^n+c is divisible by d^2
• Skip the discrete log where d = p.

That would mean that all factors found by the discrete log divide both k*b^n+c and (k*b^n+c)/d.

I don't know when I can complete this, but it is the best I can offer at this time.

I coded my own slower sieve so this is low priority, I'll also play around and see if I can hack mtsieve to work for my specific case.

[SethTro]

Originally Posted by rogue

Sorry, but I have not. I am mainly stuck on how to handle terms that are not divisible by the divisor. For example if you had (3^n-1)/5, then how do I handle terms where 3^n-1 is not already divisible by 5. I think that pfgw actually tests floor((3^n-1)/5). The challenge is two-fold. Just because p divides 3^n-1 for some value of n, it doesn't mean that p divides floor(3^n-1)/5 for that same value of n. The converse is also true. p could divide floor(3^n-1)/5, but does not divide 3^n-1. The algorithm behind srsieve2 works by finding factors of 3^n-1 so it cannot find some of the factors that would divide floor((3^n-1)/5).

Given the values you have for k, b, c, and d, 3^n-7 is always even, so always divisible by 2. I could make a change to support sieving sequences meeting these criteria:

• d is prime
• d evenly divides all k*b^n+c terms

I would then need to:

• Remove all terms where k*b^n+c is divisible by d^2
• Skip the discrete log where d = p.

That would mean that all factors found by the discrete log divide both k*b^n+c and (k*b^n+c)/d.

I don't know when I can complete this, but it is the best I can offer at this time.

I coded my own slower sieve so this is low priority, I'll also play around and see if I can hack mtsieve to work for my specific case (I agree with your analysis of what would need to be done)

I'm surprised that pfgw takes the floor of the division. I have no idea what you should do in that case.

[SethTro]

I found the source of my problem by compiling with `make DEBUG=yes` and using gdb.

The code was running from CisOneWithOneSequenceWorker which I eventually parsed in the symbolic domain as "C Is One" instead of just a random identifier.

void SierpinskiRieselApp::ValidateOptions(void)
{
   seq_t     *seqPtr;
   ib_CanUseCIsOneLogic = true;

Critically this is called AFTER AddSequence resetting ib_CanUseCIsOneLogic

void  SierpinskiRieselApp::AddSequence(uint64_t k, int64_t c, uint32_t d)
{
...
   uint64_t absc = abs(c);
   if (absc != 1)
      ib_CanUseCIsOneLogic = false;

I can "fix" the invalid factors issue by commenting out the assignment to true. I suspect you're the person who should figure out the correct fix.

[rogue]

AddSequence() should be called before MakeSubsequences(), which where the Helper is created. Is the wrong Helper created? It should be creating GenericSequenceHelper.

[SethTro]

Originally Posted by rogue

AddSequence() should be called before MakeSubsequences(), which where the Helper is created. Is the wrong Helper created? It should be creating GenericSequenceHelper.

The flow I'm seeing is

core/main:main calls
ProcessArgs calls
SierpinskiRieselApp::ParseOptions calls
SierpinskiRieselApp::ValidateAndAddNewSequence calls
SierpinskiRieselApp::AddSequence
where ib_CanUseCIsOneLogic set false

after that

core/main:main calls
core/App:Run calls
SierpinskiRieselApp::ValidateOptions
which resets ib_CanUseCIsOneLogic = true;
then calls
SierpinskiRieselApp::MakeSubsequences
which creates CisOneWithOneSequenceHelper
when it should be creating GenericSequenceHelper

it feels like `ib_CanUseCIsOneLogic = true;` should probably be moved to the constructor

Index: sierpinski_riesel/SierpinskiRieselApp.cpp
===================================================================
--- sierpinski_riesel/SierpinskiRieselApp.cpp    (revision 205)
+++ sierpinski_riesel/SierpinskiRieselApp.cpp    (working copy)
@@ -48,6 +48,8 @@
    SetAppMinPrime(3);
    SetAppMaxPrime(PMAX_MAX_62BIT);
 
+   ib_CanUseCIsOneLogic = true;
+
    ii_MinN = 0;
    ii_MaxN = 0;
    it_Format = FF_ABCD;
@@ -233,7 +235,6 @@
 void SierpinskiRieselApp::ValidateOptions(void)
 {
    seq_t     *seqPtr;
-   ib_CanUseCIsOneLogic = true;
 
    if (it_Format == FF_UNKNOWN)
       FatalError("the specified file format in not valid, use A (ABC), D (ABCD), P (ABC with number_primes), or B (BOINC)");

[sweety439]

Can you update mtsieve to make it be able to sieve the sequence (a*b^n+c)/gcd(a+c,b-1) with gcd(a+c,b-1) > 1 (for a>=1, b>=2, c != 0, gcd(a,c) = 1, gcd(b,c) = 1)?

e.g. (113*13^n-5)/12, which has no single known prime or PRP, and is the number 9555...555 with n 5's in base 13, if such prime exists, then the smallest such prime would be a minimal prime (start with b+1) in base b = 13, see this page

For this family, one would sieve the sequence 113*13^n-5 for primes not dividing 12, i.e. sieve starting with the prime 5 (and ending with 10^9 or more), and initialized the list of candidates to not include n for which 2 or 3 divides (113*13^n-5)/12

Most of the unsolved families in the "minimal prime problem" require this updating, e.g. the unsolved families in base 19 and the unsolved families in base 21

[rogue]

I see what you are saying. The line in ValidateOptions should be in the constructor. Thanks for finding it.

[rogue]

Originally Posted by sweety439

Can you update mtsieve to make it be able to sieve the sequence (a*b^n+c)/gcd(a+c,b-1) with gcd(a+c,b-1) > 1 (for a>=1, b>=2, c != 0, gcd(a,c) = 1, gcd(b,c) = 1)?

e.g. (113*13^n-5)/12, which has no single known prime or PRP, and is the number 9555...555 with n 5's in base 13, if such prime exists, then the smallest such prime would be a minimal prime (start with b+1) in base b = 13, see this page

For this family, one would sieve the sequence 113*13^n-5 for primes not dividing 12, i.e. sieve starting with the prime 5 (and ending with 10^9 or more), and initialized the list of candidates to not include n for which 2 or 3 divides (113*13^n-5)/12

Most of the unsolved families in the "minimal prime problem" require this updating, e.g. the unsolved families in base 19 and the unsolved families in base 21

The answer at this time is "no". I stated above the limitations I can add to srsieve2. What you are asking for doesn't meet the criteria that I listed above (d must be prime and d must divide k*b^n+c for all n). It looks like SethTho is going to get that working. More investigation needs to be done to support other conditions. For example I think that pfgw uses floor(), but it might use round() or ceil(). I have to figure that out before doing anything along the lines of what you are asking.

In the interim, if you know C++, you can possibly investigate writing your own sieve based upon the framework.

[sweety439]

Originally Posted by rogue

The answer at this time is "no". I stated above the limitations I can add to srsieve2. What you are asking for doesn't meet the criteria that I listed above (d must be prime and d must divide k*b^n+c for all n). It looks like SethTho is going to get that working. More investigation needs to be done to support other conditions. For example I think that pfgw uses floor(), but it might use round() or ceil(). I have to figure that out before doing anything along the lines of what you are asking.

In the interim, if you know C++, you can possibly investigate writing your own sieve based upon the framework.

Then, can we use mtsieve to sieve the sequence 113*13^n-5 with the primes p>=5 (and initialized the list of candidates to not include n for which 2 or 3 divides (113*13^n-5)/12, i.e. only include the n == 2, 4 mod 6)? Or it will return error as every term is divisible by 12?

[rogue]

Originally Posted by sweety439

Then, can we use mtsieve to sieve the sequence 113*13^n-5 with the primes p>=5 (and initialized the list of candidates to not include n for which 2 or 3 divides (113*13^n-5)/12, i.e. only include the n == 2, 4 mod 6)? Or it will return error as every term is divisible by 12?

I cannot tell you. I haven't determined the behavior to use yet. That is much easier said than done. I don't know when I am going to look into it.