mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Conjectures 'R Us (https://www.mersenneforum.org/forumdisplay.php?f=81)
-   -   Conjectured K question (https://www.mersenneforum.org/showthread.php?t=25177)

dannyridel 2020-02-05 12:27

Conjectured K question
 
How do you calculate the conjectured K for each base?

sweety439 2020-02-05 20:27

[QUOTE=dannyridel;536747]How do you calculate the conjectured K for each base?[/QUOTE]

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)))
[/CODE]

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)))
[/CODE]

NHoodMath 2020-02-05 22:51

[QUOTE=dannyridel;536747]How do you calculate the conjectured K for each base?[/QUOTE]
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.

gd_barnes 2020-02-06 00:41

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.

Dylan14 2020-02-06 01:50

[QUOTE=gd_barnes;536832]
If anyone can post a link to the covering or bigcovering programs that would be helpful.[/QUOTE]

Here you go: [URL]https://sites.google.com/site/robertgerbicz/coveringsets[/URL]

dannyridel 2020-02-06 02:47

I'm in China....
No google, no discord, no youtube, blahblahblah

NHoodMath 2020-02-06 03:17

[QUOTE=gd_barnes;536832]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.[/QUOTE]

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!)

dannyridel 2020-02-06 03:41

:lol:
Though I still can't access Google...:groan:

VBCurtis 2020-02-06 03:53

[QUOTE=NHoodMath;536845] 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!)[/QUOTE]

We should not wait until 2079 to get started!

LaurV 2020-02-06 05:24

Or just skip it... (we have plenty of work to do) :cmd:
(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)

henryzz 2020-02-06 09:31

1 Attachment(s)
[QUOTE=dannyridel;536848]:lol:
Though I still can't access Google...:groan:[/QUOTE]

Here they are.


All times are UTC. The time now is 13:23.

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