 mersenneforum.org Williams' sequence 4*5^n-1 (A046865)
 Register FAQ Search Today's Posts Mark Forums Read  2006-07-21, 00:49   #12

Jun 2005

3×11 Posts Quote:
 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

Last fiddled with by konrad127123 on 2006-07-21 at 00:51   2006-07-21, 15:53   #13
Citrix

Jun 2003

110001100012 Posts Quote:
 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.   2006-07-21, 20:17 #14 konrad127123   Jun 2005 3·11 Posts 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. Last fiddled with by konrad127123 on 2006-07-21 at 20:46   2006-07-21, 21:15 #15 Citrix   Jun 2003 5×317 Posts 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.   2006-07-21, 23:32   #16

Jun 2005

3·11 Posts Quote:
 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)   2006-07-22, 04:47 #17 Citrix   Jun 2003 110001100012 Posts 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.   2006-07-24, 02:58   #18
geoff

Mar 2003
New Zealand

13×89 Posts Quote:
 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.   2006-07-25, 03:40   #19
geoff

Mar 2003
New Zealand

13×89 Posts Quote:
 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.   2006-07-25, 05:37   #20
Citrix

Jun 2003

158510 Posts Quote:
 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.   2006-07-25, 22:59 #21 Citrix   Jun 2003 5×317 Posts 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? Last fiddled with by Citrix on 2006-07-25 at 23:29   2006-07-26, 03:01   #22
geoff

Mar 2003
New Zealand

115710 Posts Quote:
 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.   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post kar_bon Aliquot Sequences 136 2021-10-21 16:17 devarajkandadai Miscellaneous Math 3 2020-12-01 22:08 sweety439 And now for something completely different 17 2017-06-13 03:49 Sam Kennedy Miscellaneous Math 4 2013-02-07 11:53 roger Puzzles 16 2006-10-18 19:52

All times are UTC. The time now is 16:40.

Wed Dec 8 16:40:23 UTC 2021 up 138 days, 11:09, 1 user, load averages: 1.90, 1.56, 1.58