mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Blogorrhea > sweety439

Reply
 
Thread Tools
Old 2016-12-14, 12:16   #1
sweety439
 
sweety439's Avatar
 
Nov 2016

178410 Posts
Default 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 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.
Attached Files
File Type: txt extend-Sierp-base3.txt (3.4 KB, 49 views)
File Type: txt extend-Sierp-base4.txt (2.8 KB, 46 views)
File Type: txt extend-Riesel-base3.txt (3.4 KB, 58 views)
File Type: txt extend-Riesel-base4.txt (50 Bytes, 44 views)
File Type: txt Conjectured smallest strong Sierpinski Riesel number to base b.txt (729 Bytes, 83 views)

Last fiddled with by sweety439 on 2018-10-22 at 11:54
sweety439 is offline   Reply With Quote
Old 2016-12-14, 20:38   #2
gd_barnes
 
gd_barnes's Avatar
 
May 2007
Kansas; USA

5×2,017 Posts
Default

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
gd_barnes is offline   Reply With Quote
Old 2016-12-15, 04:58   #3
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

837010 Posts
Default

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 View Post
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

Last fiddled with by LaurV on 2016-12-15 at 05:04 Reason: found it!
LaurV is offline   Reply With Quote
Old 2016-12-15, 13:36   #4
sweety439
 
sweety439's Avatar
 
Nov 2016

23·223 Posts
Default

Quote:
Originally Posted by gd_barnes View Post
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 is offline   Reply With Quote
Old 2016-12-15, 16:28   #5
sweety439
 
sweety439's Avatar
 
Nov 2016

23×223 Posts
Default

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
sweety439 is offline   Reply With Quote
Old 2016-12-15, 17:05   #6
sweety439
 
sweety439's Avatar
 
Nov 2016

110111110002 Posts
Default

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
File Type: txt extend-Riesel-base7.txt (3.1 KB, 58 views)
File Type: txt extend-Sierp-base7.txt (1.4 KB, 56 views)

Last fiddled with by sweety439 on 2016-12-15 at 17:42
sweety439 is offline   Reply With Quote
Old 2016-12-15, 17:20   #7
sweety439
 
sweety439's Avatar
 
Nov 2016

23×223 Posts
Default

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
File Type: txt extend-Sierp-base10.txt (6.7 KB, 127 views)
File Type: txt extend-Riesel-base10.txt (2.2 KB, 62 views)

Last fiddled with by sweety439 on 2017-06-27 at 19:15
sweety439 is offline   Reply With Quote
Old 2016-12-15, 17:27   #8
sweety439
 
sweety439's Avatar
 
Nov 2016

6F816 Posts
Default

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
File Type: txt extend-Sierp-base12.txt (3.5 KB, 40 views)
File Type: txt extend-Riesel-base12.txt (135 Bytes, 63 views)

Last fiddled with by sweety439 on 2016-12-15 at 17:29
sweety439 is offline   Reply With Quote
Old 2016-12-15, 18:28   #9
sweety439
 
sweety439's Avatar
 
Nov 2016

23·223 Posts
Default

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

Last fiddled with by sweety439 on 2016-12-15 at 18:36
sweety439 is offline   Reply With Quote
Old 2016-12-15, 18:35   #10
sweety439
 
sweety439's Avatar
 
Nov 2016

23·223 Posts
Default

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

All these conjectures are easily to prove.
Attached Files
File Type: txt extend-Sierp-base5,8,9,11.txt (254 Bytes, 37 views)
File Type: txt extend-Riesel-base5,8,9,11.txt (187 Bytes, 63 views)

Last fiddled with by sweety439 on 2016-12-15 at 18:37
sweety439 is offline   Reply With Quote
Old 2016-12-15, 18:42   #11
sweety439
 
sweety439's Avatar
 
Nov 2016

23×223 Posts
Default

Can you find the smallest conjectured strong Sierpinski number in base 3 and 6?
sweety439 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Semiprime and n-almost prime candidate for the k's with algebra for the Sierpinski/Riesel problem sweety439 sweety439 10 2018-12-14 21:59
The reverse Sierpinski/Riesel problem sweety439 sweety439 11 2018-06-11 07:21
The dual Sierpinski/Riesel problem sweety439 sweety439 12 2017-12-01 21:56
Sierpinski/ Riesel bases 6 to 18 robert44444uk Conjectures 'R Us 139 2007-12-17 05:17
Sierpinski/Riesel Base 10 rogue Conjectures 'R Us 11 2007-12-17 05:08

All times are UTC. The time now is 01:40.

Mon Mar 30 01:40:27 UTC 2020 up 4 days, 23:13, 2 users, load averages: 1.01, 1.16, 1.30

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.