A Sierpinski/Riesel-like problem

[sweety439]

For the original Sierpinski/Riesel problem, it is finding and proving the smallest k such that k*b^n+-1 is composite for all integer n>=1 and gcd(k+-1, b-1) = 1. Now, I extend to the k's such that gcd(k+-1, b-1) is not 1. Of course, all numbers of the form k*b^n+-1 is divisible by gcd(k+-1, b-1). Thus, I must take out this factor and find and prove the smallest k such that (k*b^n+-1)/gcd(k+-1, b-1) is composite for all integer n>=1. (of course, in the base 2 case, this is completely the same as the original Sierpinski/Riesel problem)

In the original Sierpinski/Riesel problems, k-values with all n-values have a single trivial factor are excluded from the conjectures. However, in these problems, we take out this trivial factor, thus all k-values are included from the conjectures. (thus, in this problems, the divisor of k*b^n+-1 is the largest trivial factor of k*b^n+-1, which equals gcd(k+-1, b-1))

The research is form http://mersenneforum.org/showthread.php?t=21832.

The Riesel case are also researched in https://www.rose-hulman.edu/~rickert/Compositeseq/.

The strong (extended) Sierpinski problem base 4 is proven, with the conjectured k=419. Also, the strong (extended) Riesel problem base 10 is proven, with the conjectured k=334.

For the strong (extended) Riesel problem base 3, for k<=500, I cannot find a prime for k = {119, 313, 357}. For k=291, the prime is the same as the k=97 prime: (97*3^3131-1)/2, since 291 = 97*3, and since 357 = 119*3, the prime for k=357 is the same as the prime for k=119, but both are unknown.

Edit: According to the link, (313*3^24761-1)/2 is a probable prime.

Extended Sierpinski problem base b: Finding and proving the smallest integer k>=1 such that (k*b^n+1)/gcd(k+1, b-1) is not prime for all integer n>=1.

Extended Riesel problem base b: Finding and proving the smallest integer k>=1 such that (k*b^n-1)/gcd(k-1, b-1) is not prime for all integer n>=1.

The last text file is the list of the conjectured smallest strong Sierpinski/Riesel number number to base b for b = 2 to b = 12.

[gd_barnes]

For the strong (extended) Riesel problem base 3, for k<=500, I cannot find a prime for k = {119, 313, 357}. For k=291, the prime is the same as the k=97 prime: (97*3^3131-1)/2, since 291 = 97*3, and since 357 = 119*3, the prime for k=357 is the same as the prime for k=119, but both are unknown.

Edit: According to the link, (313*3^24761-1)/2 is a probable prime.

I would suggest keeping this in the "And now for something completely different" sub-forum. It does not apply to CRUS. If you want some smaller (not top-10) primes that CRUS has found I have already said that I'll give them to you.

Someone put a lot of effort into the page that you linked to but there is a lot of inconsistency in how the k-values are being shown both in that link and in your post here for base 3 append 1. It creates a lot of confusion over what needs to be searched.

First suggestion: When showing which k's need a prime use the k-value in this form:
k*3^n+(3^n-1)/2

Reasoning for the suggestion. For a more complex base/append combination, such as base 9 append 7, it would not be clear what k is being searched unless you use the form:
k*9^n+(9^n-1)*7/8

Second suggestion: Do not show k=3m as remaining. It is redundant.

Using that format, what you are asking for are PRPs for k= {59, 156}. Here they are:

59*3^8972+(3^8972-1)/2 is PRP
156*3^24761+(3^24761-1)/2 is PRP

The author of the site that you linked to did not do a good job of consistency in how he displayed his k's remaining and primes. K's should properly be reduced to their lowest form lest they end up as higher than the actual conjecture. For instance many of his k's and PRP's for base 3 append 1 are k==(1 mod 3). Such k's can be reduced to (k-1)/3 while adding 1 to the n-value. (Many can be reduced multiple times.) Here are two related examples that would have helped you on both of the above PRP's:

1. k=4819 with a PRP at n=8968 is the same as and should be shown as k=59 with a PRP at n=8972.
2. k=4225 with a PRP at n=24758 is the same as and should be shown as k=156 with a PRP at n=24761.

Had he shown these PRP's in correct reduced format you would have realized that you already had the PRPs that you were looking for.

This goes to the crux of the problem when running projects or asking others for help with your efforts: It is important that you are very clear and consistent else people get confused and become disinterested in helping.

Back to the page that you linked to: Note that he searched all base 3 append 1 k's to n=50K. I double checked him to n=25K. k=806 is the smallest k remaining at n=50K. His results are correct except that his k's are shown in the inconsistent format demonstrated above. For example he shows that the following "single k's" are remaining:
(806, 2419)
(915, 2746)
In other words the second number is the first number * 3 + 1, which will result in the same prime, so he is avoiding searching both k's. That is a good thing BUT...
he is missing that k=5383 should show:
(1794, 5383)

Someone double checking the base (like me) could easily conclude that k=1794 is remaining and think that he had missed it. In other words k==(1 mod 3) needs to be reduced for consistency and the same applies to the primes that he shows as demonstrated above.

The linked page is extremely old and inconsistent. You should consider doing some of your own double checking on it and check for other inconsistencies or errors.

[LaurV]

It shows you put some time and effort into that reply! But... What is the English equivalent of "a strica orzul pe gâște"? (rhetoric question, no answer needed) (edit: found it! the linked thread is nice to read, my answer is in posts #7, #10, etc in that thread)

Originally Posted by gd_barnes

Had he shown these PRP's in correct reduced format you would have realized that you already had the PRPs that you were looking for.
<snip>
The linked page is extremely old and inconsistent. You should consider doing some of your own double checking on it and check for other inconsistencies or errors.

+1

[sweety439]

Originally Posted by gd_barnes

I would suggest keeping this in the "And now for something completely different" sub-forum. It does not apply to CRUS. If you want some smaller (not top-10) primes that CRUS has found I have already said that I'll give them to you.

Someone put a lot of effort into the page that you linked to but there is a lot of inconsistency in how the k-values are being shown both in that link and in your post here for base 3 append 1. It creates a lot of confusion over what needs to be searched.

First suggestion: When showing which k's need a prime use the k-value in this form:
k*3^n+(3^n-1)/2

Reasoning for the suggestion. For a more complex base/append combination, such as base 9 append 7, it would not be clear what k is being searched unless you use the form:
k*9^n+(9^n-1)*7/8

Second suggestion: Do not show k=3m as remaining. It is redundant.

Using that format, what you are asking for are PRPs for k= {59, 156}. Here they are:

59*3^8972+(3^8972-1)/2 is PRP
156*3^24761+(3^24761-1)/2 is PRP

The author of the site that you linked to did not do a good job of consistency in how he displayed his k's remaining and primes. K's should properly be reduced to their lowest form lest they end up as higher than the actual conjecture. For instance many of his k's and PRP's for base 3 append 1 are k==(1 mod 3). Such k's can be reduced to (k-1)/3 while adding 1 to the n-value. (Many can be reduced multiple times.) Here are two related examples that would have helped you on both of the above PRP's:

1. k=4819 with a PRP at n=8968 is the same as and should be shown as k=59 with a PRP at n=8972.
2. k=4225 with a PRP at n=24758 is the same as and should be shown as k=156 with a PRP at n=24761.

Had he shown these PRP's in correct reduced format you would have realized that you already had the PRPs that you were looking for.

This goes to the crux of the problem when running projects or asking others for help with your efforts: It is important that you are very clear and consistent else people get confused and become disinterested in helping.

Back to the page that you linked to: Note that he searched all base 3 append 1 k's to n=50K. I double checked him to n=25K. k=806 is the smallest k remaining at n=50K. His results are correct except that his k's are shown in the inconsistent format demonstrated above. For example he shows that the following "single k's" are remaining:
(806, 2419)
(915, 2746)
In other words the second number is the first number * 3 + 1, which will result in the same prime, so he is avoiding searching both k's. That is a good thing BUT...
he is missing that k=5383 should show:
(1794, 5383)

Someone double checking the base (like me) could easily conclude that k=1794 is remaining and think that he had missed it. In other words k==(1 mod 3) needs to be reduced for consistency and the same applies to the primes that he shows as demonstrated above.

The linked page is extremely old and inconsistent. You should consider doing some of your own double checking on it and check for other inconsistencies or errors.

Unfortunately, it is only for the extend-Riesel problem, not the extend-Sierpinski problem.

[sweety439]

In these conjectures, the form is (k*b^n+-1)/gcd(k+-1,b-1). Thus, for example, for the extended Riesel problem base 38 and k=1, the form is (1*38^n-1)/gcd(1-1, 38-1) = (1*38^n-1)/37. Thus, the corresponding prime is not 1*38^1-1, it is (1*38^3-1)/37.

[sweety439]

R7 (extended) has only one k remain: 197. (its conjecture is k=457)

Some (probable) primes not in the text file are given in the link:

(159*7^4896-1)/2
(313*7^5907-1)/6
(367*7^15118-1)/6
(429*7^3815-1)/2

Besides, according to the link, (197*7^n-1)/2 is checked to n=15000 with no (probable) prime found. Thus, this conjecture is nearly proven.

The extended S7 conjecture is easily to proven, with k=209 the smallest strong Sierpinski number to base 7.

The extended R4, S5, R5, S8, R8, S9, R9, S11, R11 and R12 conjectures are trivial and very easily to proven.

[sweety439]

The conjecture of S10 (extended) is k=989, with a covering set {3, 7, 11, 13}, period=6.

I tested the conjecture and it has only 3 k's remain: 100, 269, and 804. However, k=100 is a GFN, for k=804, it is a prime given by the CRUS: 804*10^5470+1. Thus, only k=269 is remain, the form is (269*10^n+1)/9.

Also, the conjecture of R10 (extended) is k=334, with a covering set {3, 7, 13, 37}, period=6. This conjecture can be easily to proven.

[sweety439]

The conjecture of S12 (extended) is proven, since only GFNs (k=12 and k=144) are remain.

The conjecture of R12 (extended) is easily to proven.

Thus, the only harder conjecture is the extended conjecture of S2, R2, S3, R3, S6, and R6. (the base 2 extended Sierpinski/Riesel conjecture is completely the same as the original base 2 Sierpinski/Riesel conjecture)

[sweety439]

Update the extended S6/R6 files. (only up to k=500)

[sweety439]

Update the extend Sierpinski/Riesel conjectures base 5, 8, 9, 11 files.

All these conjectures are easily to prove.

[sweety439]

Can you find the smallest conjectured strong Sierpinski number in base 3 and 6?