Williams' sequence 4*5^n-1 (A046865)

[konrad127123]

Originally Posted by Citrix

Can b-1 ever be a sierpinki or riesel number for base b?

I've proved that if b-1 is a Sierpinski or a Riesel number for base b then it must have an infinite covering set. I can post the proof here if someone wants it.

It might be possible to find a b such that (b-1)*b^n+/-1 factorises nicely for some n (e.g. 4*5^6-1=(2*5^3-1)*(2*5^3+1)) with the rest of the n's having a finite covering set, but I haven't managed yet. I'm still looking into it.

Also, I'm working on the 5*6^n-1 sequence:
5*6^11233-1 & 5*6^13363-1 are both prime with no further primes below 14500

[Citrix]

Originally Posted by konrad127123

I've proved that if b-1 is a Sierpinski or a Riesel number for base b then it must have an infinite covering set. I can post the proof here if someone wants it.

Could you post this or PM it to me?

Thank you.

[konrad127123]

We will treat the Riesel and Sierpinski cases separately (the first part applies to both cases).

Suppose for contradiction, that we have a b, with a finite covering set (for n>0) S={p_1, p_2, ..., p_k}. We can assume wlog (without loss of generality) that all the p_i's are prime. If p_i|b for some i then p_i does not divide (b-1)*b^n+-1. So we can assume wlog that p_i does not divide b for any i. Also, for n>0, (b-1)*b^n+/-1 cannot be even so we can assume that 2 is not in S (this avoids S={2}, which would be a special case for the argument below)

For each n (we have assumed that) there exists a p_i in our set S such that p_i|(b-1)*b^n+/-1.

Riesel case:
consider when n=((p_1-1)*(p_2-1)*...*(p_k-1))-1
If there is an i for which p_i|(b-1)*b^n-1 then
1=(b-1)*b^((p_i-1)*c-1) mod p_i (for some positive integer c)
so b=(b-1)*b^((p_i-1)*c) mod p_i
=((b-1)*1^c) mod p_i (by Fermat's little theorem, since p_i does not divide b)
=(b-1) mod p_i
so 0=-1 mod p_i. Contradiction! Therefore such a b cannot exist (for Riesels).

Sierpinski Case:
This is quite similar. In this case we let n=((p_1-1)*(p_2-1)*...*(p_k-1))
If there is an i for which p_i|(b-1)*b^n+1 then
-1=(b-1)*b^((p_i-1)*c) mod p_i (for some positive integer c)
=((b-1)*1^c) mod p_i (by Fermat's little theorem, since p_i does not divide b)
=(b-1) mod p_i
so b=0 mod p_i
So p_i|b. But we assumed that p_i did not divide b. Contradiction!
Therefore such a b cannot exist (for Siepinskis).

Thus we can't have such a b with a finite covering set, so if there exists a b such that (b-1) is Riesel (or Sierpinski) base b, it must have an infinite covering set.

[Citrix]

Your proof is interesting, but flawed.

1=(b-1)*b^((p_i-1)*c-1) mod p_i (for some positive integer c)

C does not exist for all p_i. Hence these p_i can form the covering set.
Your proof if it was correct says that all b-1*b^n-+1 numbers are prime. Which is not true.

[konrad127123]

Originally Posted by Citrix

1=(b-1)*b^((p_i-1)*c-1) mod p_i (for some positive integer c)

C does not exist for all p_i. Hence these p_i can form the covering set.
Your proof if it was correct says that all b-1*b^n-+1 numbers are prime. Which is not true.

c does exist. c=(p_1-1)*(p_2-1)*...*(p_(i-1)-1)*(p_(i+1)-1)*...*(p_k-1) or (equivalently) c=((p_1-1)*(p_2-1)*...*(p_k-1))/(p_i-1)

If there is an i for which p_i|(b-1)*b^n-1 then
(b-1)*b^(((p_1-1)*(p_2-1)*...*(p_k-1))-1)-1=0 mod p_i
so 1=(b-1)*b^(((p_1-1)*(p_2-1)*...*(p_k-1))-1) mod p_i
=(b-1)*b^((p_i-1)*c-1) mod p_i (for some positive integer c)


My proof definitely does not sat that all such numbers are prime. It says that if you can't cover every value of n for a particular b with a *finite* covering set. It requires an infinite covering set. My proof also doesn't show that (b-1) can never be a Riesel/Sierpinski base b. It does show that if you try to find a b such that b-1 is riesel or sierpinski base b, it just says that you can't find one by looking for just a finite covering set.

(I'm not sure if it was clear or not, but p_j is meant to represent p subscript j)

[Citrix]

Geoff,

A quick question for you. If you consider 4*5^n+1. All n's left after sieving till 3 are multiples of 2 ie. all numbers left are x^2+1. Note that numbers of the form x^(2^y)+1 are generalized fermats and have factors of the form K*2^(Y+1)+1

So for 4*5^n+1 you only have to consider p=4*K+1. This makes sieving twice as fast compared to sieving for all primes.

I am currently working on 625. only numbers of the form 625*2^(4*n) are left. So all factors are of the form p=8K+1. I was wondering is it possible to make the srsieve only consider these special factors and hence make the sieve faster than newpgen.

Thank you in advance for the answer.

[geoff]

Originally Posted by Citrix

I was wondering is it possible to make the srsieve only consider these special factors and hence make the sieve faster than newpgen.

Thanks for that suggestion :-) I will have a go at implementing it soon.

[geoff]

Originally Posted by Citrix

I am currently working on 625. only numbers of the form 625*2^(4*n) are left. So all factors are of the form p=8K+1. I was wondering is it possible to make the srsieve only consider these special factors and hence make the sieve faster than newpgen.

Even with this idea it seems that NewPGen will still be faster than srsieve for base 2 sequences. At least two base-2 sequences will have to be sieved at once (both with factors of the same form) before srsieve catches up.

[Citrix]

Originally Posted by geoff

Even with this idea it seems that NewPGen will still be faster than srsieve for base 2 sequences. At least two base-2 sequences will have to be sieved at once (both with factors of the same form) before srsieve catches up.

NO problem, I plan to do several of them.
http://www.mersenneforum.org/showthread.php?t=6038

[Citrix]

I am not completely sure, but I think jjsieve already does this for me. k=25 seems faster to sieve than k=5. So I think you do not have to implement anything.

I think when you do discrete log, based on factors of p-1, the first factor 2, eliminates the primes if it does not have the right power of 2 in p-1.


edit:
I am working on k=3^16 for base 2^16 from 0 to 2 Million, I am getting about 2150kp/s on a 1.4 ghz p4. What would the speed be for your program, with the above implementation ie. only considering primes 32*a+1?

[geoff]

Originally Posted by Citrix

II am working on k=3^16 for base 2^16 from 0 to 2 Million, I am getting about 2150kp/s on a 1.4 ghz p4. What would the speed be for your program, with the above implementation ie. only considering primes 32*a+1?

I have implemented your idea in srsieve version 0.3.12, if you use the --verbose switch it will print a message like "Filtering for primes of the form ..." if the special form of the sequence is recognised.

There is one limitation that I may be able to remove in the future: If you sieve two sequences together like (7^2)*2^n+1 and (7^4)*2^n+1, it will sieve both sequences using the same form of factors, i.e. p=x*2^2+1 in this case. If you sieve (7^4)*2^n+1 seperately it can use p=x*2^3+1.