mersenneforum.org A Sierpinski/Riesel-like problem
 Register FAQ Search Today's Posts Mark Forums Read

2016-12-14, 12:16   #1
sweety439

Nov 2016

87216 Posts
A Sierpinski/Riesel-like problem

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 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.
Attached Files
 extend-Sierp-base3.txt (3.4 KB, 65 views) extend-Sierp-base4.txt (2.8 KB, 62 views) extend-Riesel-base3.txt (3.4 KB, 72 views) extend-Riesel-base4.txt (50 Bytes, 63 views) Conjectured smallest strong Sierpinski Riesel number to base b.txt (729 Bytes, 99 views)

Last fiddled with by sweety439 on 2018-10-22 at 11:54

2016-12-14, 20:38   #2
gd_barnes

May 2007
Kansas; USA

100111110000002 Posts

Quote:
 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.

Last fiddled with by gd_barnes on 2016-12-15 at 00:58

2016-12-15, 04:58   #3
LaurV
Romulan Interpreter

Jun 2011
Thailand

5·11·157 Posts

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)
Quote:
 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. 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

Last fiddled with by LaurV on 2016-12-15 at 05:04 Reason: found it!

2016-12-15, 13:36   #4
sweety439

Nov 2016

2×23×47 Posts

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

 2016-12-15, 16:28 #5 sweety439     Nov 2016 2×23×47 Posts 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. Last fiddled with by sweety439 on 2017-02-07 at 14:29
2016-12-15, 17:05   #6
sweety439

Nov 2016

41628 Posts

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.
Attached Files
 extend-Riesel-base7.txt (3.1 KB, 75 views) extend-Sierp-base7.txt (1.4 KB, 73 views)

Last fiddled with by sweety439 on 2016-12-15 at 17:42

2016-12-15, 17:20   #7
sweety439

Nov 2016

216210 Posts

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.
Attached Files
 extend-Sierp-base10.txt (6.7 KB, 143 views) extend-Riesel-base10.txt (2.2 KB, 79 views)

Last fiddled with by sweety439 on 2017-06-27 at 19:15

2016-12-15, 17:27   #8
sweety439

Nov 2016

2×23×47 Posts

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)
Attached Files
 extend-Sierp-base12.txt (3.5 KB, 55 views) extend-Riesel-base12.txt (135 Bytes, 78 views)

Last fiddled with by sweety439 on 2016-12-15 at 17:29

2016-12-15, 18:28   #9
sweety439

Nov 2016

2×23×47 Posts

Update the extended S6/R6 files. (only up to k=500)
Attached Files
 extend-Sierp-base6.txt (3.3 KB, 57 views) extend-Riesel-base6.txt (3.3 KB, 53 views)

Last fiddled with by sweety439 on 2016-12-15 at 18:36

2016-12-15, 18:35   #10
sweety439

Nov 2016

41628 Posts

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

All these conjectures are easily to prove.
Attached Files
 extend-Sierp-base5,8,9,11.txt (254 Bytes, 53 views) extend-Riesel-base5,8,9,11.txt (187 Bytes, 79 views)

Last fiddled with by sweety439 on 2016-12-15 at 18:37

2016-12-15, 18:42   #11
sweety439

Nov 2016

2·23·47 Posts

Can you find the smallest conjectured strong Sierpinski number in base 3 and 6?
Attached Files
 Conjectured smallest strong Sierpinski Riesel number to base b.txt (762 Bytes, 65 views)

 Similar Threads Thread Thread Starter Forum Replies Last Post sweety439 sweety439 20 2020-07-03 17:22 sweety439 sweety439 10 2018-12-14 21:59 sweety439 sweety439 12 2017-12-01 21:56 robert44444uk Conjectures 'R Us 139 2007-12-17 05:17 rogue Conjectures 'R Us 11 2007-12-17 05:08

All times are UTC. The time now is 15:53.

Wed Aug 12 15:53:52 UTC 2020 up 26 days, 11:40, 3 users, load averages: 1.81, 2.20, 2.23