- **Open Projects**
(*https://www.mersenneforum.org/forumdisplay.php?f=80*)

- - **Williams' sequence 4*5^n-1 (A046865)**
(*https://www.mersenneforum.org/showthread.php?t=6131*)

[QUOTE=Citrix]
Can b-1 ever be a sierpinki or riesel number for base b? [/QUOTE] 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 |

[QUOTE=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.
[/QUOTE] Could you post this or PM it to me? Thank you. |

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. |

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. |

[QUOTE=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.[/QUOTE] 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) |

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. |

[QUOTE=Citrix]I was wondering is it possible to make the srsieve only consider these special factors and hence make the sieve faster than newpgen.[/QUOTE]
Thanks for that suggestion :-) I will have a go at implementing it soon. |

[QUOTE=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.[/QUOTE]
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. |

[QUOTE=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.[/QUOTE]
NO problem, I plan to do several of them. [url]http://www.mersenneforum.org/showthread.php?t=6038[/url] |

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? |

[QUOTE=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?[/QUOTE]
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. |

All times are UTC. The time now is 02:42. |

Powered by vBulletin® Version 3.8.11

Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.