User group for PFGW & PrimeForm programs
Yahoo Group

Sierpinski / Riesel base 2^x+1

===============================================
Robert     Message 1 of 4  Sep 26, 2004
-----------------------------------------------
Following on to my post on Sierpinski/ Riesel base 5, it seems worth 
exploring the various Sierpinski and Riesel numbers base 2^x+1, 
where x is an integer. 

These (3,5,9,17,33...) are the only bases which do not provide 
trivial even k solutions. Why is that? No doubt someone will tell 
me! It is, of course, only a conjecture at this stage.

Even so, the base sets are generally simple. My (and others) results 
so far are (I hope my table posts sensibly):

Number		Candidates left		Covering set	
Sierp	Riesel	Sierp	Riesel	Sierpinski	Riesel

5	159986	346802	230	c600	3,7,13,31,601	3,7,13,31,601
9	2344	74	4	4	5,7,13,73	5,7,13,73
17	278	86	4	0	3,5,29	        3,5,29
33	1854	764	14	9	5,7,17,109	5,7,17,109
65	10	10	0	0	3,11	        3,11
129	14	14	1	1	5,13     	5,13
257	44	44	4	0	3,43    	3,43
513	??	??				
1025	20	20	0	2	3,19    	3,19
2049	124	124	11	11	5,41    	5,41
4097	94	682?	17	110	3,5,7,13,19	3,683

513 has given me gyp, because there are so many choices of potential 
covering sets, but the obvious candidates do not have the right 
congruences. Maybe someone will solve that. The 4097 Riesel is only 
a maybe. The others need checking, but I think they are the 
smallest. 

Those with only two members in the covering set share the same k 
value, but other than that there is not much to observe. 

The column showing "Candidates left" is after a shallow check for 
primes, and therefore shows those with no small primes. But these 
numbers get big quickly, for example, 4*9^n-1 is not prime up to 
n=83606 (the only number I have checked to any depth), so actually 
showing that 74.9^n-1 is the Riesel number base 9 may prove beyond 
us, who knows! 

Regards

Robert Smith
===============================================
David Broadhurst     Message 2 of 4  Sep 26, 2004
-----------------------------------------------
Robert:

> These (3,5,9,17,33...) are the only bases which do not provide
> trivial even k solutions. Why is that? 

Consider any odd base b that is _not_ of the form 2^x+1.

Then b-1 is divisible by at least one odd prime, say q.

So q-1 is a Sierpinski number:

(q-1)*b^n+1=0 mod q for all n

and q+1 is a Riesel number:

(q+1)*b^n-1=0 mod q for all n

since b=1 mod q.

David
===============================================
David Broadhurst     Message 3 of 4  Sep 26, 2004
-----------------------------------------------
The only reason that b=2^x+1 is nontrivial, for x>0,
is the fact that you demand the multiplier k, in 

k*b^n -/+ 1,

to be even, i.e.

k != +/-1 mod 2

So why not generalize your "exclusion principle" to
exclude the trivial residue classes +/-1 modulo 
*all* of the prime divisors of b-1? 

Then you have the same game to play in every odd base, not so?

For example: 

Search for k such that
k != +1 mod 2 [you do this already!]
k != +1 mod 3 [so why not this also?]
k*7^n - 1 is always composite

Search for k such that
k != -1 mod 2 [you do this already!]
k != -1 mod 3 [so why not this also?]
k*7^n + 1 is always composite

Search for k such that
k != +1 mod 2 [you do this already!]
k != +1 mod 3 [so why not this also?]
k != +1 mod 5 [and this also!]
k*31^n - 1 is always composite

Search for k such that
k != -1 mod 2 [you do this already!]
k != -1 mod 3 [so why not this also?]
k != -1 mod 5 [and this also!]
k*31^n + 1 is always composite

At present you have an exponential explosion
of supposedly "non-trivial" bases because you 
exclude the trivial residue classes modulo only
one of the prime divisors of b-1, namely modulo 2.

If you want to progress sub-exponentially,
the appropriate "generalized exclusion principle" 
should be clear from the above, not so?

David (per proxy Wolfgang Pauli)
===============================================
Shane     Message 4 of 4  Sep 27, 2004
-----------------------------------------------
David wrote,
> The only reason that b=2^x+1 is nontrivial, for x>0,
> is the fact that you demand the multiplier k, in 
> k*b^n -/+ 1,
> to be even, i.e.
> k != +/-1 mod 2

Sounds like you're speaking to me.
Obviously not directly, but this is verbatim what the generalized RMA 
sequence is.
ID Number: A084924
URL:       http://www.research.att.com/projects/OEIS?Anum=A084924

Non-triavial in respect to base two.
Since RMA, is only for base two, and the upcoming ASA, will be for 
multiple bases.  The real non-trivial sequence is given by ASA.
Anchored-Sieving-Algorithm.
===============================================
Cached by Georg Fischer at Nov 14 2019 12:47 with clean_yahoo.pl V1.4