mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2020-07-11, 03:58   #1
Gelly
 
Gelly's Avatar
 
May 2020

22·3 Posts
Talking Numbers Sierpinski to multiple bases

Hello! This question errs on the side of not-number-theory, so I'll ask it here.

Given that Brier numbers (numbers that are Sierpinski and Riesel) exist and can be made by considering different covering sets, I was curious as to how far it could be reasonably extended.

For a start, could there be a number that is Sierpinski to 2 and 3? I imagine it's relatively easy - just find the right sorts of covering sets and zip them together - but how small could we reasonably expect the smallest one to be? On the scale of known Brier numbers?

What if we extend it to 2, 3, and 5? How about arbitrarily many primes? Can this sort of process of multibase Sierpinski numbers be able to be extended forever for the set of primes, or is there a hard limit? Is there a way to use Aurifeuillean-based Sierpinski numbers to guarentee covering sets that work together well for the primes?

I'm aware that "the set of powers of 2" is already an infinite set for which a k exists that is Sierpinski to all of them (or, really, any set of powers of some base), but how much can we do with other sets?

Thanks,

Gelly
Gelly is offline   Reply With Quote
Old 2020-07-14, 07:28   #2
JeppeSN
 
JeppeSN's Avatar
 
"Jeppe"
Jan 2016
Denmark

2·71 Posts
Thumbs up

I agree with you it should be possible to find "simultaneous" Sierpinski numbers to multiple bases, by picking disjoint covering sets (one covering set for the first base, and a non-overlapping covering set for the second base).

The precise definition of Sierpinski to base b is important, of course. For base b=3, most people exclude the trivial examples where k is odd. Because then a set with just one prime in it covers, namely { 2 }. So to be Sierpinski to base 3 and base 2, you would have to accept an even Sierpinski number to base 2.

Brunner, Caldwell, Krywaruczenko and Lownsdale require a Sierpinski k to base b to have the property gcd(k+1, b-1) = 1 (to avoid covering sets with one prime) and also the property that k is not a rational power of b.

The second property is to avoid generalized Fermat sequences for which only exponents of the form two to something, can produce primes. For example, if b = 1000, then taking k = 10000, leading to 10000*1000^n + 1, would be excluded by the definition by Caldwell et al. Because 10000 = 1000^(4/3). And in essence you would be looking at candidates 10^(2^m) + 1, and we do not think they will yield primes for m > 1 (although we cannot prove it).

Enough smalltalk with no answer to your question! Come on, everybody, have you ever located a number that was Sierpinski to two "nonrelated" bases?

/JeppeSN
JeppeSN is offline   Reply With Quote
Old 2020-07-14, 14:45   #3
Gelly
 
Gelly's Avatar
 
May 2020

22·3 Posts
Default

Just in case it's missed elsewhere, I had a minor discussion/revelation about the "infinite set" problem that has a pretty trivial solution.

For bases of the form 15n+14, k=4 is Sierpinski to all of those bases. This is easily realized by the fact that 15n+14 is -1 mod 3 and -1 mod 5, where 4 is 1 mod 3 and -1 mod 5. For odd powers of the base, you have (1)*(-1)+1 = 0 mod 3, and for even powers of the base you have (-1)*(1)+1 = 0 mod 5.

Fitting the gcd property below, k+1 is 5 and b-1 is 15n+13, so they will always be coprime as well. Therefore, 4 is Sierpinski to all bases of the form 15n+14, which is not only an infinite set, but also a nonzero density one, too. Using different two prime covering sets can also lead to k with other sets, such as k = 20 (covering set {3, 19} and bases 57n+56, n =/= 7m+1). Perhaps you can combine some of these trivially to make much larger sets, but that might be asking too much.

I'm sure this is trivial for anyone who spends an iota of time on things like CRUS, but it's a pleasant revelation for me and answers one of my questions.
Gelly is offline   Reply With Quote
Old 2020-07-14, 15:22   #4
sweety439
 
sweety439's Avatar
 
Nov 2016

5×431 Posts
Default

Quote:
Originally Posted by JeppeSN View Post
I agree with you it should be possible to find "simultaneous" Sierpinski numbers to multiple bases, by picking disjoint covering sets (one covering set for the first base, and a non-overlapping covering set for the second base).
Also, k's making a full covering set with all or partial algebraic factors are not consider as Sierpinski/Riesel numbers, since they do not have a single set of fixed numeric factors. e.g. 8 is not considered as Sierpinski number base 27, and 2500 is not considered as Sierpinski number base 55, see http://www.noprimeleftbehind.net/cru...onjectures.htm and https://mersenneforum.org/showthread.php?t=21763

Last fiddled with by Uncwilly on 2020-07-14 at 20:11 Reason: TRIM YOUR QUOTES!
sweety439 is offline   Reply With Quote
Old 2020-07-14, 15:30   #5
sweety439
 
sweety439's Avatar
 
Nov 2016

5·431 Posts
Default

Quote:
Originally Posted by JeppeSN View Post
I agree with you it should be possible to find "simultaneous" Sierpinski numbers to multiple bases, by picking disjoint covering sets (one covering set for the first base, and a non-overlapping covering set for the second base).
I also have another definition of Sierpinski/Riesel numbers extended to the k such that gcd(k+-1,b-1) (+ for Sierpinski, - for Riesel) is not 1, since k*b^n+-1 is always divisible by gcd(k+-1,b-1), it is simple to take out this factor and use "numbers k such that (k*b^n+-1)/gcd(k+-1,b-1) is not prime for all n>=1 (k's making a full covering set with all or partial algebraic factors are not considered), see https://mersenneforum.org/showthread...=21839&page=75, https://docs.google.com/document/d/e...UF8OgSUVsS/pub, https://docs.google.com/document/d/e...8HDWrvEC82/pub and https://github.com/xayahrainie4793/E...el-conjectures

Last fiddled with by Uncwilly on 2020-07-14 at 20:12 Reason: TRIM YOUR QUOTES!
sweety439 is offline   Reply With Quote
Old 2020-07-14, 15:56   #6
sweety439
 
sweety439's Avatar
 
Nov 2016

5·431 Posts
Default

This is the conjectured smallest Sierpinski/Riesel number in new definition to base b for 2<=b<=2048, "NA" if the smallest such number is > 10^6

Original definition: k's such that k*b^n+-1 (+ for Sierpinski, - for Riesel) is not prime for n>=1 and gcd(k+-1,b-1) (+ for Sierpinski, - for Riesel) = 1

New definition: k's such that (k*b^n+-1)/gcd(k+-1,b-1) (+ for Sierpinski, - for Riesel) is not prime for n>=1

Brunner, Caldwell, Krywaruczenko and Lownsdale exclude the k's which is a rational power of b, I do not exclude these k's but exclude the k's making a full covering set with all or partial algebraic factors (e.g. (1*4^n-1)/3, (1*9^n-1)/8, 4*9^n-1, (4*19^n-1)/3, 4*24^n-1, (4*34^n-1)/3, 9*4^n-1, 9*14^n-1, 9*24^n-1, 6*24^n-1, 6*54^n-1, (1*8^n-1)/7, 27*8^n-1, 8*27^n-1, 1*8^n+1, (1*27^n+1)/2, 1*32^n+1, (1*32^n-1)/31, (27*8^n+1)/7, 8*27^n+1, (4*16^n+1)/5, (4*81^n+1)/5, 4*625^n+1, (324*16^n+1)/5, (64*81^n+1)/5, 2500*16^n+1, 2500*81^n+1, etc.), I also exclude the k's that do not make a full covering set with all or partial algebraic factors but have no possible prime (e.g. 8*128^n+1, 32*128^n+1, (27*2187^n+1)/2, etc.)

I include this k for this Sierpinski/Riesel base b if and only if this k may have infinitely many primes.
Attached Files
File Type: txt Sierpinski.txt (17.7 KB, 1 views)
File Type: txt Riesel.txt (17.8 KB, 1 views)

Last fiddled with by sweety439 on 2020-07-14 at 16:06
sweety439 is offline   Reply With Quote
Old 2020-07-14, 16:01   #7
sweety439
 
sweety439's Avatar
 
Nov 2016

5×431 Posts
Default

Conjecture 1 (the strong Sierpinski conjecture): For b>=2, k>=1, if there is an n such that:

(1) k*b^n is neither a perfect odd power (i.e. k*b^n is not of the form m^r with odd r>1) nor of the form 4*m^4.
(2) gcd((k*b^n+1)/gcd(k+1,b-1),(b^(945*2^s)-1)/(b-1)) = 1 for all s, i.e. for all s, every prime factor of (k*b^n+1)/gcd(k+1,b-1) does not divide (b^(945*2^s)-1)/(b-1). (i.e. ord_p(b) is not of the form 2^r (r>=0 if p = 2 or p = 3, r>=1 if p>=5) or m*2^r (m divides 945, r>=0) for every prime factor p of (k*b^n+1)/gcd(k+1,b-1)).
(3) this (k,b) pair is not the case: b = q^m, k = q^r, where q is not of the form t^s with odd s>1, and m and r have no common odd prime factor, and the exponent of highest power of 2 dividing r >= the exponent of highest power of 2 dividing m, and the equation 2^x = r (mod m) has no solution. (the first 6 Sierpinski bases with k's which are this case are 128, 2187, 16384, 32768, 78125 and 131072)

Then there are infinitely many primes of the form (k*b^n+1)/gcd(k+1,b-1).

Conjecture 2 (the strong Riesel conjecture): For b>=2, k>=1, if there is an n such that:

(1) k*b^n is not a perfect power (i.e. k*b^n is not of the form m^r with r>1).
(2) gcd((k*b^n-1)/gcd(k-1,b-1),(b^(945*2^s)-1)/(b-1)) = 1 for all s, i.e. for all s, every prime factor of (k*b^n-1)/gcd(k-1,b-1) does not divide (b^(945*2^s)-1)/(b-1). (i.e. ord_p(b) is not of the form 2^r (r>=0 if p = 2 or p = 3, r>=1 if p>=5) or m*2^r (m divides 945, r>=0) for every prime factor p of (k*b^n-1)/gcd(k-1,b-1)).

Then there are infinitely many primes of the form (k*b^n-1)/gcd(k-1,b-1).
sweety439 is offline   Reply With Quote
Old 2020-07-14, 17:50   #8
sweety439
 
sweety439's Avatar
 
Nov 2016

41538 Posts
Default

Quote:
Originally Posted by Gelly View Post
Just in case it's missed elsewhere, I had a minor discussion/revelation about the "infinite set" problem that has a pretty trivial solution.
See post https://mersenneforum.org/showpost.p...&postcount=853

Last fiddled with by Uncwilly on 2020-07-14 at 20:12 Reason: TRIM YOUR QUOTES!
sweety439 is offline   Reply With Quote
Old 2020-07-15, 16:58   #9
sweety439
 
sweety439's Avatar
 
Nov 2016

5×431 Posts
Default

Quote:
Originally Posted by sweety439 View Post
Also, k's making a full covering set with all or partial algebraic factors are not consider as Sierpinski/Riesel numbers, since they do not have a single set of fixed numeric factors. e.g. 8 is not considered as Sierpinski number base 27, and 2500 is not considered as Sierpinski number base 55, see http://www.noprimeleftbehind.net/cru...onjectures.htm and https://mersenneforum.org/showthread.php?t=21763
I only think the k's having a single set of fixed numeric factors as Sierpinski/Riesel numbers, thus I do not think these k's for (1*4^n-1)/3, (1*9^n-1)/8, 4*9^n-1, (4*19^n-1)/3, 4*24^n-1, (4*34^n-1)/3, 9*4^n-1, 9*14^n-1, 9*24^n-1, 6*24^n-1, 6*54^n-1, (1*8^n-1)/7, 27*8^n-1, 8*27^n-1, 1*8^n+1, (1*27^n+1)/2, 1*32^n+1, (1*32^n-1)/31, (27*8^n+1)/7, 8*27^n+1, (4*16^n+1)/5, (4*81^n+1)/5, 4*625^n+1, (324*16^n+1)/5, (64*81^n+1)/5, 2500*16^n+1, 2500*81^n+1, etc. as Sierpinski/Riesel numbers for these bases b, nor these k's for 8*128^n+1, 32*128^n+1, (27*2187^n+1)/2 etc. as Sierpinski/Riesel numbers for these bases b
sweety439 is offline   Reply With Quote
Old 2020-07-15, 17:09   #10
sweety439
 
sweety439's Avatar
 
Nov 2016

41538 Posts
Default

Quote:
Originally Posted by sweety439 View Post
Brunner, Caldwell, Krywaruczenko and Lownsdale exclude the k's which is a rational power of b, I do not exclude these k's but exclude the k's making a full covering set with all or partial algebraic factors (e.g. (1*4^n-1)/3, (1*9^n-1)/8, 4*9^n-1, (4*19^n-1)/3, 4*24^n-1, (4*34^n-1)/3, 9*4^n-1, 9*14^n-1, 9*24^n-1, 6*24^n-1, 6*54^n-1, (1*8^n-1)/7, 27*8^n-1, 8*27^n-1, 1*8^n+1, (1*27^n+1)/2, 1*32^n+1, (1*32^n-1)/31, (27*8^n+1)/7, 8*27^n+1, (4*16^n+1)/5, (4*81^n+1)/5, 4*625^n+1, (324*16^n+1)/5, (64*81^n+1)/5, 2500*16^n+1, 2500*81^n+1, etc.), I also exclude the k's that do not make a full covering set with all or partial algebraic factors but have no possible prime (e.g. 8*128^n+1, 32*128^n+1, (27*2187^n+1)/2, etc.)

I include this k for this Sierpinski/Riesel base b if and only if this k may have infinitely many primes.
Some of more complex examples of the k's making a full covering set with all or partial algebraic factors:

25*12^n-1
27*12^n-1
64*12^n-1
(81*17^n-1)/16
144*28^n-1
(289*28^n-1)/9
(175*28^n-1)/3
16*33^n-1
(169*33^n-1)/8
(225*33^n-1)/32
(289*33^n-1)/32
81*40^n-1
(1024*40^n-1)/3
16*50^n-1
18*50^n-1
(529*52^n-1)/3
900*52^n-1
(637*52^n-1)/3
(9*57^n-1)/8
(25*57^n-1)/8
(121*57^n-1)/8
121*60^n-1
1369*30^n-1
(400*88^n-1)/3
324*95^n-1
(343*10^n-1)/9
64*957^n-1
3511808*63^n+1
27000000*63^n+1
324*2070^n+1
2500*13^n+1
2500*55^n+1
114244*225^n+1
16*200^n+1
(64*391^n-1)/3
64*936^n-1
sweety439 is offline   Reply With Quote
Old 2020-07-15, 20:51   #11
Gelly
 
Gelly's Avatar
 
May 2020

22·3 Posts
Talking

I think I found a solution for b = 2 and b = 3, by doing some hacky work to combine covering sets. I constructed the covering sets such that I could share the most primes between them, and to fill the holes with whatever else I could get away with.

Covering set for 2: {3, 5, 13, 17, 97, 241, 257} modulus 48
Covering set for 3: {5, 7, 13, 17, 41, 73, 193, 577, 769, 6481} modulus 48

In order to reconcile the three shared primes between the covering sets, I actually hand-picked the moduli so that I could get the most gas out of using them. Here’s the solutions for the covered primes given the k I calculated, k = 310905992968447463275644916

For base 2:

k2^(2n+1)+1 is divisible by 3 (k = 1 mod 3)
k2^(4n+2)+1 is divisible by 5 (k = 1 mod 5)
k2^(12n)+1 is divisible by 13 (k = 12 mod 13)
k2^(8n+4)+1 is divisible by 17 (k = 1 mod 17)
k2^(48n+16)+1 is divisible by 97 (k = 62 mod 97)
k2^(24n+8)+1 is divisible by 241 (k = 16 mod 241)
k2^(16n+8)+1 is divisible by 257 (k = 1 mod 257)

This covers the entire space for modulo 48*, and so this number is Sierpinski base 2.

For base 3:

k is not a trivial case (k = 0 mod 2)
k3^(4n+2)+1 is divisible by 5 (k = 1 mod 5)
k3^(6n+1)+1 is divisible by 7 (k = 2 mod 7)
k3^(3n)+1 is divisible by 13 (k = 12 mod 13)
k3^(16n+8)+1 is divisible by 17 (k = 1 mod 17)
k3^(8n+4)+1 is divisible by 41 (k = 1 mod 41)
k3^(12n+11)+1 is divisible by 73 (k = 70 mod 73)
k3^(16n)+1 is divisible by 193 (k = 192 mod 193)
k3^(48n+29)+1 is divisible by 577 (k = 19 mod 577)
k3^(48n+5)+1 is divisible by 769 (k = 250 mod 769)
k3^(24n+17)+1 is divisible by 6481 (k = 4294 mod 6481)

This covers the entire space for modulo 48*, and so this number is Sierpinski base 3.

I’ve tried to make sure that this is all up to snuff, double checked against all entries for both base 2 and 3 containing the factors I’d expect them to, even triple checked this post, and it all looks good to me. I imagine someone else has done this first, but I’m not sure if smaller.

This definitely can be optimized to be smaller - I hand-picked every modulus, even the ones that weren’t necessary, so it’s definitely likely that one can do a lot better with a small computer search. You would have to make sure that for the shared primes in the sets, you get maximal coverage with modulus selections, but otherwise you can pick the rest as you would with any other Sierpinski search. I would hope that the smallest one would be smaller than the smallest Brier number, since you should be able to do better with sharing more primes, but I’m not certain.

EDIT: JeppeSN helped me realize the Sierpinski modulus for each covering set was smaller than I thought. Thanks!

Last fiddled with by Gelly on 2020-07-15 at 21:23
Gelly is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Numbers in Other Bases Stargate38 Lounge 22 2020-07-15 22:41
prime power Sierpinski numbers snorton Prime Sierpinski Project 1 2015-03-25 03:07
A multiple k/c sieve for Sierpinski/Riesel problems geoff Sierpinski/Riesel Base 5 522 2009-10-28 05:46
How did they prove that Riesel/Sierpinski numbers. Unregistered Homework Help 17 2009-10-08 18:08
Sierpinski/ Riesel bases 6 to 18 robert44444uk Conjectures 'R Us 139 2007-12-17 05:17

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

Sat Aug 8 18:35:03 UTC 2020 up 22 days, 14:21, 1 user, load averages: 2.10, 1.78, 1.66

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.