Numbers Sierpinski to multiple bases

Gelly · 2020-07-11, 03:58

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

JeppeSN · 2020-07-14, 07:28

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

Gelly · 2020-07-14, 14:45

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.

sweety439 · 2020-07-14, 15:22

Quote:

Originally Posted by JeppeSN

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

sweety439 · 2020-07-14, 15:30

Quote:

Originally Posted by JeppeSN

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

sweety439 · 2020-07-14, 15:56

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.

sweety439 · 2020-07-14, 16:01

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 · 2020-07-14, 17:50

Quote:

Originally Posted by Gelly

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

sweety439 · 2020-07-15, 16:58

Quote:

Originally Posted by sweety439

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 · 2020-07-15, 17:09

Quote:

Originally Posted by sweety439

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

Gelly · 2020-07-15, 20:51

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!

2020-07-11, 03:58	#1
Gelly May 2020 26₁₀ Posts	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

2020-07-15, 20:51	#11
Gelly May 2020 2·13 Posts	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

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Numbers in Other Bases are Belong to Us	Stargate38	Lounge	44	2020-10-24 11:33
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

2020-07-14, 07:28	#2
JeppeSN "Jeppe" Jan 2016 Denmark 2²×41 Posts	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

2020-07-14, 14:45	#3
Gelly May 2020 2·13 Posts	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.

2020-07-14, 16:01	#7
sweety439 Nov 2016 2764₁₀ Posts	Conjecture 1 (the strong Sierpinski conjecture): For b>=2, k>=1, if there *is an n* such that: (1) kb^n is neither a perfect odd power (i.e. kb^n is not of the form m^r with odd r>1) nor of the form 4m^4. (2) gcd((kb^n+1)/gcd(k+1,b-1),(b^(9452^s)-1)/(b-1)) = 1 for all s, i.e. for all s, every prime factor of (kb^n+1)/gcd(k+1,b-1) does not divide (b^(9452^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 m2^r (m divides 945, r>=0) for every prime factor p of (kb^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 (kb^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) kb^n is not a perfect power (i.e. kb^n is not of the form m^r with r>1). (2) gcd((kb^n-1)/gcd(k-1,b-1),(b^(9452^s)-1)/(b-1)) = 1 for all s, i.e. for all s, every prime factor of (kb^n-1)/gcd(k-1,b-1) does not divide (b^(9452^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 m2^r (m divides 945, r>=0) for every prime factor p of (kb^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).