mersenneforum.org  

Go Back   mersenneforum.org > Other Stuff > Open Projects

Reply
 
Thread Tools
Old 2006-07-21, 00:49   #12
konrad127123
 
konrad127123's Avatar
 
Jun 2005

3×11 Posts
Default

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
konrad127123 is offline   Reply With Quote
Old 2006-07-21, 15:53   #13
Citrix
 
Citrix's Avatar
 
Jun 2003

110001100012 Posts
Default

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.
Citrix is offline   Reply With Quote
Old 2006-07-21, 20:17   #14
konrad127123
 
konrad127123's Avatar
 
Jun 2005

3·11 Posts
Default

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
konrad127123 is offline   Reply With Quote
Old 2006-07-21, 21:15   #15
Citrix
 
Citrix's Avatar
 
Jun 2003

5×317 Posts
Default

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.
Citrix is offline   Reply With Quote
Old 2006-07-21, 23:32   #16
konrad127123
 
konrad127123's Avatar
 
Jun 2005

3·11 Posts
Default

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)
konrad127123 is offline   Reply With Quote
Old 2006-07-22, 04:47   #17
Citrix
 
Citrix's Avatar
 
Jun 2003

110001100012 Posts
Default

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.
Citrix is offline   Reply With Quote
Old 2006-07-24, 02:58   #18
geoff
 
geoff's Avatar
 
Mar 2003
New Zealand

13×89 Posts
Default

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.
geoff is offline   Reply With Quote
Old 2006-07-25, 03:40   #19
geoff
 
geoff's Avatar
 
Mar 2003
New Zealand

13×89 Posts
Default

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.
geoff is offline   Reply With Quote
Old 2006-07-25, 05:37   #20
Citrix
 
Citrix's Avatar
 
Jun 2003

158510 Posts
Default

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.
http://www.mersenneforum.org/showthread.php?t=6038
Citrix is offline   Reply With Quote
Old 2006-07-25, 22:59   #21
Citrix
 
Citrix's Avatar
 
Jun 2003

5×317 Posts
Default

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
Citrix is offline   Reply With Quote
Old 2006-07-26, 03:01   #22
geoff
 
geoff's Avatar
 
Mar 2003
New Zealand

115710 Posts
Default

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.
geoff is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Reserved for MF - Sequence 276 kar_bon Aliquot Sequences 136 2021-10-21 16:17
A new sequence devarajkandadai Miscellaneous Math 3 2020-12-01 22:08
Primes in n-fibonacci sequence and n-step fibonacci sequence sweety439 And now for something completely different 17 2017-06-13 03:49
Fun Sequence Sam Kennedy Miscellaneous Math 4 2013-02-07 11:53
What's the next in the sequence? 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.