mersenneforum.org Cullen prime problem
 Register FAQ Search Today's Posts Mark Forums Read

 2006-12-01, 22:08 #12 Siemelink     Jan 2006 Hungary 26810 Posts I am currently sieving with Multisieve Woodall numbers. I use the range from 1.3 million to 2 million. I still have 30,000 candidates left. Do I understand this discussion correctly that Multisieve is not really meant for such a range? If this is so, how can I sieve quicker? Citrix, would your sieve be amendable to do Woodalls? Or should I stick with Multisieve but switch to short ranges (10,000) containing 500 candidates? Have a nice day, Willem.
2006-12-01, 23:58   #13
rogue

"Mark"
Apr 2003
Between here and the

2×3×983 Posts

Quote:
 Originally Posted by Siemelink I am currently sieving with Multisieve Woodall numbers. I use the range from 1.3 million to 2 million. I still have 30,000 candidates left. Do I understand this discussion correctly that Multisieve is not really meant for such a range? If this is so, how can I sieve quicker? Citrix, would your sieve be amendable to do Woodalls? Or should I stick with Multisieve but switch to short ranges (10,000) containing 500 candidates? Have a nice day, Willem.
MultiSieve is fine for that range since you are sieving all n in that range. If you were only sieving where n is a prime, then Citrix's code would have the advantage.

2006-12-02, 05:04   #14
maxal

Feb 2005

22·32·7 Posts

Quote:
 Originally Posted by maxal P.P.S. There is another speed up possible if we replace p-1 with the multiplicative order of 2 modulo p (that is a divisor of p-1). So, instead of letting k go from 0 to p-2, we compute incrementally and store values u[i]=2^i mod p, i=1,2,... until we get u[z]=1, meaning that z is the multiplicative order of 2 modulo p. Then we let k go from 0 to z-1, compute r = ((z-k) * p + u[k] * z) mod (p*z), and eliminate candidates r, r + (p*z), r + 2*(p*z), ..., up to selected upper bound.
Correction: r = ((z-k) * p + u[k] * (p-1)) mod (p*z)

 2006-12-26, 05:42 #15 Citrix     Jun 2003 2·5·157 Posts @ rouge. I was able to modify your program yesterday, to suit my needs, but it did not become as fast as we thought it would have become. I just increased the size of the array that stores all the values of 2^1, 2^2... (mod p). Though I did see some speed up. I am not sure how to speed up the program further. Any thoughts. Also something is wrong with the time function. The time per candidate keeps on jumping between 15 sec and 60 secs. (I did not modify this code, so its not me)
2006-12-26, 13:39   #16
rogue

"Mark"
Apr 2003
Between here and the

2×3×983 Posts

Quote:
 Originally Posted by Citrix @ rouge. I was able to modify your program yesterday, to suit my needs, but it did not become as fast as we thought it would have become. I just increased the size of the array that stores all the values of 2^1, 2^2... (mod p). Though I did see some speed up. I am not sure how to speed up the program further. Any thoughts. Also something is wrong with the time function. The time per candidate keeps on jumping between 15 sec and 60 secs. (I did not modify this code, so its not me)
Is as fast as your code? If not, is there anything you see that could be modified to help? I wonder if the compiler you are using is smart enough to optimize the code correctly so that the ASM routines I have written do not provide any benefit (and might actually hurt performance). The code was written to be fairly generic, so it doesn't take advantage of any CPU specific optimizations. I would expect that you would see the biggest benefit for p > 2^31.

I'm not aware of any issues with the timing code. If you find something let me know.

2006-12-26, 19:56   #17
Citrix

Jun 2003

2·5·157 Posts

Quote:
 Originally Posted by rogue Is as fast as your code? If not, is there anything you see that could be modified to help? I wonder if the compiler you are using is smart enough to optimize the code correctly so that the ASM routines I have written do not provide any benefit (and might actually hurt performance). The code was written to be fairly generic, so it doesn't take advantage of any CPU specific optimizations. I would expect that you would see the biggest benefit for p > 2^31. I'm not aware of any issues with the timing code. If you find something let me know.
It is about as fast as my program. My program only computes upto 2^31, so there is no way to compare on speeds after that. As for the compiler, I am using VC++ 6.0. Is there a better compiler I could use? I am testing both programs on a 1.4 Ghz intel celeron processor.

Currently I have only sieved upto 350M. (The sieve is quite slow, about 80M/hr. Not sure if this series will be worth testing.) So, it will be a long time before I cross 2^31, and if the program gets slower after that....

For the timing issue I think it depends on the distribution of factors. Sometimes 10 factors are found in a min and then no factors for 5+ mins. I think this would screw up the timing?

 2007-01-31, 08:26 #18 ATH Einyen     Dec 2003 Denmark 3·977 Posts I sieved cullen numbers from n=1 to n=5,000,000 up to 2.5G (2.5 * 109). I found 4,847,529 factors so that leaves 152,457 unknowns plus the 14 known cullen primes. Here is all 5 million n's with factors: cullenfactors.zip (18 Mb). The 14 primes have "PRIME" instead of a factor, and the 152,457 unknowns have "?" instead of a factor. Here is ABC format file for the 109,042 unknowns between n=1,500,000 (current progress according to http://www.prothsearch.net/cullenrange.html ) and n=5,000,000: cullen1.5M-5M.zip
 2007-01-31, 19:22 #19 alpertron     Aug 2002 Buenos Aires, Argentina 52A16 Posts p*2p+1 cannot be prime if p>3 is a prime twin. First suppose p=1 (mod 3) and let p=2q+1 (because p is odd). Operating modulo 3 we find: p*2p+1 = 1*22q+1+1 = 22q*2+1 = (22)q*2+1 = 1q*2+1 = 2+1 = 0 (mod 3) The other possibility is p=2 (mod 3) and p+2 also a prime. Operating modulo p+2 we find: p*2p+1 = (-2)*2p+1 = -2p+1+1 = -1+1 = 0 (mod p+2) So in both cases p*2p+1 is composite.
2007-02-01, 01:17   #20
brunoparga

Feb 2006
BrasÃ­lia, Brazil

3×71 Posts

Dario,

Modular arithmetic still looks like a strange realm to me. So, I'm not sure if I understand what you've written:
Quote:
 Originally Posted by alpertron p*2p+1 = 1*22q+1+1 = 22q*2+1 = (22)q*2+1 = 1q*2+1 = 2+1 = 0 (mod 3)
In short, does this mean no prime p = 1 (mod 3) can generate a Cullen prime? Even if this p isn't a prime twin?

Quote:
 Originally Posted by alpertron p*2p+1 = (-2)*2p+1 = -2p+1+1 = -1+1 = 0 (mod p+2)
I can't understand the part I've put in bold. Since both sides have a "+1" term, I assume I can change that particular equality to:

-2p+1 = -1 (mod p+2)

I still can't understand it even if I multiply both sides by (-1) (can I do that?), giving:

2p+1 = 1 (mod p+2)

Testing with small primes, I can see it works. But why?

Thanks a lot,
Bruno

2007-02-01, 03:59   #21
ATH
Einyen

Dec 2003
Denmark

3·977 Posts

Quote:
 Originally Posted by brunoparga 2p+1 = 1 (mod p+2)
This is just Fermat's Little Theorem with p+2 = prime (p being twin prime) and a=2.

2007-02-01, 12:14   #22
alpertron

Aug 2002
Buenos Aires, Argentina

101001010102 Posts

Quote:
 Originally Posted by brunoparga In short, does this mean no prime p = 1 (mod 3) can generate a Cullen prime? Even if this p isn't a prime twin?
In that case p does not need to be prime. When p=1 (mod 3) the argument shown above demonstrates that p*2p+1 is multiple of 3.

Last fiddled with by alpertron on 2007-02-01 at 12:15

 Similar Threads Thread Thread Starter Forum Replies Last Post rogue And now for something completely different 29 2019-11-20 14:01 jasong jasong 9 2008-01-25 01:51 jasong Marin's Mersenne-aries 1 2007-11-18 23:17 hhh Prime Cullen Prime 4 2007-09-21 16:34 Citrix Prime Cullen Prime 12 2007-04-26 19:52

All times are UTC. The time now is 21:11.

Fri Sep 18 21:11:28 UTC 2020 up 8 days, 18:22, 1 user, load averages: 1.50, 1.92, 1.82