20060721, 00:49  #12  
Jun 2005
3·11 Posts 
Quote:
It might be possible to find a b such that (b1)*b^n+/1 factorises nicely for some n (e.g. 4*5^61=(2*5^31)*(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^n1 sequence: 5*6^112331 & 5*6^133631 are both prime with no further primes below 14500 Last fiddled with by konrad127123 on 20060721 at 00:51 

20060721, 15:53  #13  
Jun 2003
2^{2}·397 Posts 
Quote:
Thank you. 

20060721, 20:17  #14 
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_ib for some i then p_i does not divide (b1)*b^n+1. So we can assume wlog that p_i does not divide b for any i. Also, for n>0, (b1)*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(b1)*b^n+/1. Riesel case: consider when n=((p_11)*(p_21)*...*(p_k1))1 If there is an i for which p_i(b1)*b^n1 then 1=(b1)*b^((p_i1)*c1) mod p_i (for some positive integer c) so b=(b1)*b^((p_i1)*c) mod p_i =((b1)*1^c) mod p_i (by Fermat's little theorem, since p_i does not divide b) =(b1) 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_11)*(p_21)*...*(p_k1)) If there is an i for which p_i(b1)*b^n+1 then 1=(b1)*b^((p_i1)*c) mod p_i (for some positive integer c) =((b1)*1^c) mod p_i (by Fermat's little theorem, since p_i does not divide b) =(b1) mod p_i so b=0 mod p_i So p_ib. 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 (b1) is Riesel (or Sierpinski) base b, it must have an infinite covering set. Last fiddled with by konrad127123 on 20060721 at 20:46 
20060721, 21:15  #15 
Jun 2003
2^{2}·397 Posts 
Your proof is interesting, but flawed.
1=(b1)*b^((p_i1)*c1) 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 b1*b^n+1 numbers are prime. Which is not true. 
20060721, 23:32  #16  
Jun 2005
21_{16} Posts 
Quote:
If there is an i for which p_i(b1)*b^n1 then (b1)*b^(((p_11)*(p_21)*...*(p_k1))1)1=0 mod p_i so 1=(b1)*b^(((p_11)*(p_21)*...*(p_k1))1) mod p_i =(b1)*b^((p_i1)*c1) 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 (b1) can never be a Riesel/Sierpinski base b. It does show that if you try to find a b such that b1 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) 

20060722, 04:47  #17 
Jun 2003
11000110100_{2} 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. 
20060724, 02:58  #18  
Mar 2003
New Zealand
13·89 Posts 
Quote:


20060725, 03:40  #19  
Mar 2003
New Zealand
13×89 Posts 
Quote:


20060725, 05:37  #20  
Jun 2003
2^{2}×397 Posts 
Quote:
http://www.mersenneforum.org/showthread.php?t=6038 

20060725, 22:59  #21 
Jun 2003
2^{2}·397 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 p1, the first factor 2, eliminates the primes if it does not have the right power of 2 in p1. 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 20060725 at 23:29 
20060726, 03:01  #22  
Mar 2003
New Zealand
13·89 Posts 
Quote:
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  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Reserved for MF  Sequence 276  kar_bon  Aliquot Sequences  164  20220815 15:46 
A new sequence  devarajkandadai  Miscellaneous Math  3  20201201 22:08 
Primes in nfibonacci sequence and nstep fibonacci sequence  sweety439  sweety439  17  20170613 03:49 
Fun Sequence  Sam Kennedy  Miscellaneous Math  4  20130207 11:53 
What's the next in the sequence?  roger  Puzzles  16  20061018 19:52 