Cullen prime problem

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

[rogue]

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.

[maxal]

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)

[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)

[rogue]

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.

[Citrix]

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?

[ATH]

I sieved cullen numbers from n=1 to n=5,000,000 up to 2.5G (2.5 * 10⁹). 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

[alpertron]

p*2^p+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*2^p+1 = 1*2^2q+1+1 = 2^2q*2+1 = (2²)^q*2+1 = 1^q*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*2^p+1 = (-2)*2^p+1 = -2^p+1+1 = -1+1 = 0 (mod p+2)

So in both cases p*2^p+1 is composite.

[brunoparga]

Dario,

Modular arithmetic still looks like a strange realm to me. So, I'm not sure if I understand what you've written:

Originally Posted by alpertron

p*2^p+1 = 1*2^2q+1+1 = 2^2q*2+1 = (2²)^q*2+1 = 1^q*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?

Originally Posted by alpertron

p*2^p+1 = (-2)*2^p+1 = -2^p+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:

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

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

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

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

Thanks a lot,
Bruno

[ATH]

Originally Posted by brunoparga

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

This is just Fermat's Little Theorem with p+2 = prime (p being twin prime) and a=2.

[alpertron]

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*2^p+1 is multiple of 3.