mersenneforum.org  

Go Back   mersenneforum.org > Prime Search Projects > Conjectures 'R Us

Reply
 
Thread Tools
Old 2020-02-05, 12:27   #1
dannyridel
 
"AMD YES!"
Jan 2020
Bellevue, WA

508 Posts
Default Conjectured K question

How do you calculate the conjectured K for each base?
dannyridel is offline   Reply With Quote
Old 2020-02-05, 20:27   #2
sweety439
 
sweety439's Avatar
 
Nov 2016

22×13×37 Posts
Default

Quote:
Originally Posted by dannyridel View Post
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)))
sweety439 is offline   Reply With Quote
Old 2020-02-05, 22:51   #3
NHoodMath
 
Jan 2017

2·13 Posts
Default

Quote:
Originally Posted by dannyridel View Post
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
NHoodMath is offline   Reply With Quote
Old 2020-02-06, 00:41   #4
gd_barnes
 
gd_barnes's Avatar
 
May 2007
Kansas; USA

13·19·41 Posts
Default

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
gd_barnes is online now   Reply With Quote
Old 2020-02-06, 01:50   #5
Dylan14
 
Dylan14's Avatar
 
"Dylan"
Mar 2017

22·32·13 Posts
Default

Quote:
Originally Posted by gd_barnes View Post
If anyone can post a link to the covering or bigcovering programs that would be helpful.
Here you go: https://sites.google.com/site/robert...z/coveringsets
Dylan14 is offline   Reply With Quote
Old 2020-02-06, 02:47   #6
dannyridel
 
"AMD YES!"
Jan 2020
Bellevue, WA

4010 Posts
Default

I'm in China....
No google, no discord, no youtube, blahblahblah
dannyridel is offline   Reply With Quote
Old 2020-02-06, 03:17   #7
NHoodMath
 
Jan 2017

110102 Posts
Default

Quote:
Originally Posted by gd_barnes View Post
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!)
NHoodMath is offline   Reply With Quote
Old 2020-02-06, 03:41   #8
dannyridel
 
"AMD YES!"
Jan 2020
Bellevue, WA

4010 Posts
Default


Though I still can't access Google...
dannyridel is offline   Reply With Quote
Old 2020-02-06, 03:53   #9
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

3×7×199 Posts
Default

Quote:
Originally Posted by NHoodMath View Post
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!
VBCurtis is offline   Reply With Quote
Old 2020-02-06, 05:24   #10
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

23·11·97 Posts
Default

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)
LaurV is offline   Reply With Quote
Old 2020-02-06, 09:31   #11
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT)

566010 Posts
Default

Quote:
Originally Posted by dannyridel View Post

Though I still can't access Google...
Here they are.
Attached Files
File Type: zip covering.zip (57.7 KB, 24 views)
henryzz is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Conjectured compositeness tests for N=k⋅2n±c by Predrag T.Rex Miscellaneous Math 27 2015-10-16 19:02
Conjectured Primality Test for Specific Class of Mersenne Numbers primus Miscellaneous Math 1 2014-10-12 09:25
Conjectured Primality Test for Specific Class of k6^n-1 primus Computer Science & Computational Number Theory 16 2014-08-15 01:15
Conjectured Primality Test for 2^p-1, (2^p+1)/3 and (2^2^n+1) T.Rex Math 75 2007-09-04 07:53

All times are UTC. The time now is 11:35.

Fri May 29 11:35:42 UTC 2020 up 65 days, 9:08, 0 users, load averages: 1.11, 1.34, 1.38

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.