A Sierpinski/Riesel-like problem

[LaurV]

Originally Posted by sweety439

Conjecture: If k is not Sierpinski/Riesel in base b, then k*b is also not Sierpinski/Riesel in base b

This seems to be trivially false. It may be that \(k\cdot b^1\pm 1\) is a prime, which makes \(k\) not be a S/R, but all \(k\cdot b^n\pm 1\) (with the correspondent side plus or minus) be composite for any \(n\ge 2\), which makes \(kb\) a S/R number.

Of course, I know this is not a proof, but few counterexamples of this kind could be given to your conjecture for sure.

I remember myself not long ago (the discussion is here on the forum) being unhappy with one or two bases where one or two k's were eliminated as having primes for n=1, and trying to "re-eliminate" the respective k "properly", by finding a higher prime, so I searched from n=2 to n=200k or so, I didn't find any prime, and I gave up, running with the tail between my legs...

[sweety439]

Originally Posted by LaurV

This seems to be trivially false. It may be that \(k\cdot b^1\pm 1\) is a prime, which makes \(k\) not be a S/R, but all \(k\cdot b^n\pm 1\) (with the correspondent side plus or minus) be composite for any \(n\ge 2\), which makes \(kb\) a S/R number.

Of course, I know this is not a proof, but few counterexamples of this kind could be given to your conjecture for sure.

I remember myself not long ago (the discussion is here on the forum) being unhappy with one or two bases where one or two k's were eliminated as having primes for n=1, and trying to "re-eliminate" the respective k "properly", by finding a higher prime, so I searched from n=2 to n=200k or so, I didn't find any prime, and I gave up, running with the tail between my legs...

I conjectured that these k's eventually get a prime (the condition is that these k's does not have a covering set, or make a full covering set with all or partial algebraic factors, e.g. for (1*4^n-1)/3 (R4, k=1), it is prime only for n=2 since it has full algebraic factors)

[sweety439]

If there is no n such that k*b^n is perfect power, then (k*b^n-1)/gcd(k-1,b-1) has no algebraic factors.

If there is no n such that k*b^n is either perfect odd power (of the form m^r with odd r>1) or of the form 4*m^4, then (k*b^n+1)/gcd(k+1,b-1) has no algebraic factors.

Conjecture: If (k*b^n+-1)/gcd(k+-1,b-1) has no algebraic factors and all numbers of the form (k*b^n+-1)/gcd(k+-1,b-1) are not prime, then (k*b^n+-1)/gcd(k+-1,b-1) must have a covering set of prime factors, and all the prime factors in the covering set divides (b^576-1)/(b-1).

[sweety439]

(k*b^n-1)/gcd(k-1,b-1) has algebraic factors if and only if k*b^n is a perfect power.

(k*b^n+1)/gcd(k+1,b-1) has algebraic factors.if and only if k*b^n is either perfect odd power (of the form m^r with odd r>1) or of the form 4*m^4.

Conjecture: If all numbers of the form (k*b^n+-1)/gcd(k+-1,b-1) are not prime, then (k*b^n+-1)/gcd(k+-1,b-1) must have a covering set of prime factors for the n's such that (k*b^n+-1)/gcd(k+-1,b-1) has no algebraic factors, and all the prime factors in the covering set divides (b^576-1)/(b-1).

[sweety439]

For bases b such that b+1 = 2*p, with p odd prime, p = 3 mod 4, the smallest Sierpinski number base b is usually b+2, and the smallest Riesel number base b is usually 2*b+3. The covering set for them are both {2, p}. (although there are counterexamples, but very few, the only two counterexamples for such Sierpinski/Riesel bases b<=128 are R37 (CK=29, covering set = {2, 5, 7, 13, 67}) and R117 (CK=149, covering set = {2, 5, 37}))

[sweety439]

Conjecture: The period for the covering set for the smallest Sierpinski/Riesel number base b must divide 576. (if this conjecture is true, then all primes in the covering set satisfy that ord_p(b) divides 576, and if p divides b-1, then p=2 or p=3)

[sweety439]

Found the all CK<=10000 for all extended Sierpinski/Riesel problem bases 129<=b<=1024, the text file lists "NA" if and only if CK>10000 for this Sierpinski/Riesel base.

Note: I only tested the primes p<=30000, and I only searched (k*b^n+-1)/gcd(k+-1,b-1) for exponent n<=1500.

[sweety439]

Originally Posted by sweety439

(4*115^4223-1)/3 is (probable) prime!!!

We solved k=4 for the smallest Riesel base with k=4 remaining!!! (115 was the smallest Riesel base without known (probable) prime for k=4, excluding the bases b = 14 mod 15 (for such bases, k=4 has a covering set {3, 5}) and the bases b = m^2 (for such bases, k=4 has full algebra factors: 4*(m^2)^n-1 = (2*m^n-1) * (2*m^n+1)) and the bases b = 4 mod 5 (for such bases, k=4 has partial algebra factors: even n factors to (2*b^(n/2)-1) * (2*b^(n/2)+1), odd n has factor of 5). Now, the smallest Riesel base with k=4 remaining is 178.

Note: R72 does not have k=4 remaining, 4*72^1119849-1 is prime, see CRUS.

This is the text file for Riesel k=4 for all bases 2<=b<=256, tested to at least n=2000, there are 3 remain Riesel bases 2<=b<=256 for k=4: R178, R223 and R232 (the n's for R72, R212 and R218 are given by CRUS). In fact, I know exactly which Sierpinski/Riesel bases 2<=b<=1024 have k=1, k=2, k=3, and k=4 remaining at n=1000, even including the non-tested Sierpinski/Riesel bases, since I have tested these k's for these Sierpinski/Riesel bases to at least n=1000 (without comparing with CRUS). Besides, k=1, k=2, k=3, and k=4 for all Sierpinski/Riesel bases 2<=b<=256 have been tested to at least n=2000 by me (also without comparing with CRUS). (all of the CK's for all Sierpinski/Riesel bases 2<=b<=1024 are >= 4, i.e. no Sierpinski/Riesel bases 2<=b<=1024 have CK = 1, 2, or 3. Besides, a Sierpinski/Riesel base 2<=b<=1024 have CK = 4 if and only if b = 14 mod 15)

R107 is an interesting base, it is not only the smallest Riesel base with k=2 remaining at n=2000, but also the second smallest Riesel base with k=3 remaining at n=2000. (the smallest Riesel base with k=3 remaining at n=2000 is 42, but 3*42^2523-1 is prime).

Another interesting base is S899, this base is the only Sierpinski/Riesel base 2<=b<=1024 with all k=1, k=2, and k=3 remaining at n=1000. Besides, the CK for S899 is only 4, thus, all k < CK for this base are remaining at n=1000 (S899 is the only such Sierpinski/Riesel base 2<=b<=1024).

The bases which are excluded for the k's are:

Sierpinski k=1:

b = m^r with odd r > 1 proven composite by full algebra factors.

Sierpinski k=2:

none.

Sierpinski k=3:

none.

Sierpinski k=4:

b = 14 mod 15: covering set {3, 5}.
b = m^4 proven composite by full algebra factors.

Riesel k=1:

b = m^r with r > 1 proven composite by full algebra factors.

Riesel k=2:

none.

Riesel k=3:

none.

Riesel k=4:

b = 14 mod 15: covering set {3, 5}.
b = m^2 proven composite by full algebra factors.
b = 4 mod 5: odd n, factor of 5; even n, algebraic factors.

The first few bases remain at n=1024 for these k's are:

Sierpinski k=1:

31, 38, 50, 55, 62, 63, 67, 68, 77, 83, 86, 89, 91, 92, 97, 98, 99, 104, 107, 109, 122, 123, 127, 135, 137, 143, 144, 147, 149, ...

Sierpinski k=2:

38, 101, 104, 167, 206, 218, 236, 257, 287, 305, ...

Sierpinski k=3:

83, 123, 191, 261, 293, 303, ...

Sierpinski k=4:

32, 53, 77, 83, 107, 113, 155, 161, 174, 204, 206, 212, 227, 230, ...

Riesel k=1:

51, 91, 135, 142, 152, 174, 184, 185, 200, 230, 244, 259, 269, 281, 284, 311, ...

Riesel k=2:

107, 170, 215, 233, 254, 276, 278, 298, 303, 380, 382, 383, ...

Riesel k=3:

42, 107, 159, 283, 295, 347, 359, ...

Riesel k=4:

47, 72, 115, 163, 167, 178, 212, 218, 223, 232, 240, 270, ...

[sweety439]

Originally Posted by sweety439

Note: I don't have the prime for S46 k=283, I only know this prime is between n=15K and n=25K.

The prime for S46 k=283 is 283*46^21198+1.

[sweety439]

(11*75^3071+1)/2 is (probable) prime!!!

S75 is proven!!!

[sweety439]

(21*73^1531+1)/2 is (probable) prime!!!

S73 is now a 1k base.