mersenneforum.org Conjectured K question
 Register FAQ Search Today's Posts Mark Forums Read

 2020-02-05, 12:27 #1 dannyridel   "AMD YES!" Jan 2020 Bellevue, WA 23×5 Posts Conjectured K question How do you calculate the conjectured K for each base?
2020-02-05, 20:27   #2
sweety439

Nov 2016

25·59 Posts

Quote:
 Originally Posted by dannyridel How do you calculate the conjectured K for each base?
Using this program in PARI: (using c(n) to find the conjectured smallest Sierpinski number base n)

Code:
is(n)=forprime(p=2,50000,if(n%p==0,return(0)));1
a(n,k,b)=n*b^k+1
b(n,r)=for(k=1,5000,if(gcd(n+1,r-1)>1 || is(a(n,k,r)),return(0)));1
c(n)=for(k=1,5000000,if(b(k,n),return(k)))
Using this program in PARI: (using c(n) to find the conjectured smallest Riesel number base n)

Code:
is(n)=forprime(p=2,50000,if(n%p==0,return(0)));1
a(n,k,b)=n*b^k-1
b(n,r)=for(k=1,5000,if(gcd(n-1,r-1)>1 || is(a(n,k,r)),return(0)));1
c(n)=for(k=1,5000000,if(b(k,n),return(k)))

2020-02-05, 22:51   #3
NHoodMath

Jan 2017

2·13 Posts

Quote:
 Originally Posted by dannyridel How do you calculate the conjectured K for each base?
Sweety's code appears to be brute-forcing the CK search. Doing it rigorously requires advanced mathematics (modulo arithmetic, orders mod n, Chinese Remainder Theorem, sometimes quadratic, cubic residue analysis)
A basic outline of the steps it takes to find a CK in the easiest case (2-cover):
1) Check if there are two primes with order 2 (modulo the base)
2) Calculate b^1 and b^2 (modulo each prime)
3) Calculate the 2 possible CRT solutions (b^1 mod p1, b^2 mod p2) and (b^2 mod p1, b^1 mod p2). Whichever CRT solution is smaller is the conjectured k (unless a smaller k is found with a higher-order covering set, as is the case with many bases where the order-2 primes are 3 and some large prime in the hundreds or thousands)
There are CK's found by this project that are FAR more complex than this, just look at base 3 with a 36-cover. CK's more complex than 2- cover are best calculated using software such as Robert Gerbicz's bigcovering.exe or the Sweety PARI code below, as the number of possible covering sets and thus number of CRT solutions that need to be checked grows exponentially for each higher power.

Last fiddled with by NHoodMath on 2020-02-05 at 22:53 Reason: considering bases with 2-covering sets but which have CK's with higher order cover-sets

 2020-02-06, 00:41 #4 gd_barnes     May 2007 Kansas; USA 1012210 Posts There is a program out there called covering.exe or bigcovering.exe and there was a thread here at CRUS that talked about it. I don't have time to try to find them but with a diligent effort they can be found. You cannot brute force huge conjectures. The covering programs use covering set logic to only search k's that could possibly be the conjectures. If anyone can post a link to the covering or bigcovering programs that would be helpful. Last fiddled with by gd_barnes on 2020-02-06 at 00:43
2020-02-06, 01:50   #5
Dylan14

"Dylan"
Mar 2017

1D216 Posts

Quote:
 Originally Posted by gd_barnes If anyone can post a link to the covering or bigcovering programs that would be helpful.

 2020-02-06, 02:47 #6 dannyridel   "AMD YES!" Jan 2020 Bellevue, WA 23×5 Posts I'm in China.... No google, no discord, no youtube, blahblahblah
2020-02-06, 03:17   #7
NHoodMath

Jan 2017

1A16 Posts

Quote:
 Originally Posted by gd_barnes There is a program out there called covering.exe or bigcovering.exe and there was a thread here at CRUS that talked about it. I don't have time to try to find them but with a diligent effort they can be found. You cannot brute force huge conjectures. The covering programs use covering set logic to only search k's that could possibly be the conjectures. If anyone can post a link to the covering or bigcovering programs that would be helpful.
Just as a note so if dannyridel is interested, use covering.exe for small CK (say k<2^32) and bigcovering.exe for larger CK than 2^32. There is a bug in the covering.exe program for k's greater than some upper bound, I don't know what that bound was, I just remember it exists. (Side note, I know people back in the early days of CK searching were interested to see if there were any CK > base 280's for bases >2048. Didn't take much searching, b=2080 has a much higher CK than 280, about 10x greater. That's a base that'll be a lot of fun for the annual base searchers to look at in 60 years LOL!)

 2020-02-06, 03:41 #8 dannyridel   "AMD YES!" Jan 2020 Bellevue, WA 23·5 Posts Though I still can't access Google...
2020-02-06, 03:53   #9
VBCurtis

"Curtis"
Feb 2005
Riverside, CA

2·3·5·139 Posts

Quote:
 Originally Posted by NHoodMath b=2080 has a much higher CK than 280, about 10x greater. That's a base that'll be a lot of fun for the annual base searchers to look at in 60 years LOL!)
We should not wait until 2079 to get started!

 2020-02-06, 05:24 #10 LaurV Romulan Interpreter     Jun 2011 Thailand 100001010101102 Posts Or just skip it... (we have plenty of work to do) (this reminds us of the guy who didn't want to go to year 2000, he wanted to stay in 1999, or something like that... haha, he didn't know that the new century actually started in 2001)
2020-02-06, 09:31   #11
henryzz
Just call me Henry

"David"
Sep 2007
Cambridge (GMT)

2·3·23·41 Posts

Quote:
 Originally Posted by dannyridel Though I still can't access Google...
Here they are.
Attached Files
 covering.zip (57.7 KB, 22 views)

 Similar Threads Thread Thread Starter Forum Replies Last Post T.Rex Miscellaneous Math 27 2015-10-16 19:02 primus Miscellaneous Math 1 2014-10-12 09:25 primus Computer Science & Computational Number Theory 16 2014-08-15 01:15 T.Rex Math 75 2007-09-04 07:53

All times are UTC. The time now is 02:50.

Mon May 25 02:50:06 UTC 2020 up 61 days, 23 mins, 0 users, load averages: 1.72, 1.54, 1.37