mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Prime Cullen Prime (https://www.mersenneforum.org/forumdisplay.php?f=79)
-   -   Cullen prime problem (https://www.mersenneforum.org/showthread.php?t=6690)

 Citrix 2006-11-24 21:03

Cullen prime problem (How everything began)

On [url]http://primes.utm.edu/top20/page.php?id=6[/url]
There is an open problem to find a cullen prime p*2^p+1 where p is also prime. Has anyone done anywork on this?

I tried to write a crude sieving program. There are ~9000 candidates left under p=5 million when the range is sieved to 350 Million.

Factors available on request.

Is anyone interested in improving on these results. Writing a faster sieve software? Any thoughts on how to solve this problem?

Thanks! :smile:

 T.Rex 2006-11-24 21:15

There is a mistake on this page.
Cullen numbers are: n*2^n+1 and the last one is said to be: 338707 · 2^1354830+1 (a*2^b+1 where a!=b !!!!).
On the page:[URL="http://www.prothsearch.net/cullen.html"]Cullen Primes[/URL] it is said that the new and biggest one is: 1354828*2^1354828+1 .
T.

 smh 2006-11-24 21:30

[QUOTE=T.Rex;92304]There is a mistake on this page.
Cullen numbers are: n*2^n+1 and the last one is said to be: 338707 · 2^1354830+1 (a*2^b+1 where a!=b !!!!).
On the page:[URL="http://www.prothsearch.net/cullen.html"]Cullen Primes[/URL] it is said that the new and biggest one is: 1354828*2^1354828+1 .
T.[/QUOTE]338707*2^1354830+1 = 1354828*2^1354828+1

 T.Rex 2006-11-24 21:37

[QUOTE=smh;92307]338707*2^1354830+1 = 1354828*2^1354828+1[/QUOTE]Oh, yes!
But what a strange idea to write the number in a way different than his definition !
338707 is prime and 1354828 is the first even n satisfying n*2^n+1 .
T.

 Citrix 2006-11-24 22:57

[QUOTE=T.Rex;92309]Oh, yes!
But what a strange idea to write the number in a way different than his definition !
338707 is prime and 1354828 is the first even n satisfying n*2^n+1 .
T.[/QUOTE]

The challenge is to find p*2^p+1 so this does not qualify as a solution.:no:

 rogue 2006-11-25 01:27

[QUOTE=Citrix;92302]On [url]http://primes.utm.edu/top20/page.php?id=6[/url]
There is an open problem to find a cullen prime p*2^p+1 where p is also prime. Has anyone done anywork on this?

I tried to write a crude sieving program. There are ~9000 candidates left under p=5 million when the range is sieved to 350 Million.

Factors available on request.

Is anyone interested in improving on these results. Writing a faster sieve software? Any thoughts on how to solve this problem?

Thanks! :smile:[/QUOTE]

d/l my MultiSieve program. You can build a list of primes into an ABC file (which MultiSieve supports), then start sieving at 2.

 Citrix 2006-11-25 05:55

1 Attachment(s)
[QUOTE=rogue;92321]d/l my MultiSieve program. You can build a list of primes into an ABC file (which MultiSieve supports), then start sieving at 2.[/QUOTE]

Your program is the first thing I tried, but your program is about 10 times slower than my crude program. (A range of 1 million with n= 0 to 5 M, takes 15 sec to sieve on a intel celeron 1.5 ghz, for my program) So I think your program is not well suited for this kind of search. What do you think?

Both the programs use the same algorithm, as much as I know. Since the gap between 2 numbers remaining can be as large as 1500. I think your program, has to compute that in steps of 50 etc..., this is where it slows down. There is no way, my coding skills can be better than yours.

I have attached the abc file, try analyzing it for speed ups. Attached file is sieved upto 150 Million n=5 million. If your program finds factors under 150M, please let me know, so I can debug my program.

Thanks!:smile:

 rogue 2006-11-25 19:58

[QUOTE=Citrix;92330]Your program is the first thing I tried, but your program is about 10 times slower than my crude program. (A range of 1 million with n= 0 to 5 M, takes 15 sec to sieve on a intel celeron 1.5 ghz, for my program) So I think your program is not well suited for this kind of search. What do you think?

Both the programs use the same algorithm, as much as I know. Since the gap between 2 numbers remaining can be as large as 1500. I think your program, has to compute that in steps of 50 etc..., this is where it slows down. There is no way, my coding skills can be better than yours.[/QUOTE]

10 times? That almost sounds like an exaggeration. I suppose it is possible though. Remember, MultiSieve supports multiple bases and any n, not just where n is a prime. Since you are using only base 2, there might be base 2 tricks that I'm not using. If you send me your source I can compare our code and see if there are any tricks I can take advantage of. It has been a couple years since I've worked on the code and I have learned a few things since then, but probable not enough to account for such a huge gap. It doesn't help that I don't have any code optimization tools on x86.

 Citrix 2006-11-28 22:57

For small ranges like people at prothsearch.net work on, my program is slightly slower than yours, but when it comes to just looking cullens where the index is prime, my program becomes several times faster. I assumed this was because, your program calculated the gap in increments of 50 ... etc.

Here is the pseudo code, if you still want the real source code, it will take a while to clean it up, before I email it to you.

- generate a prime p
-calculate the maximum gap between 2 candidates
-Create array and store all values 2^1, 2^2 ... 2^max_gap (All mod p), this is done by doing *2 mod p.
- Find the largest cullen left unsieved=max. Calculated 2^(-1*max)
- Go down from the 2^(-1*max) and multiply it by gaps, consecutively and check if this value equals the index of the cullen number being tested.

I assume your program uses this algorithm. For multiplication my program uses 64 bit ints, so program is limited to 32 bits. ( haven't implemented any of the special multiplication speeds up.)

Program is compiled under, VC++ 6.0 with some optomizations selected. Not sure if that makes any difference.

What do you think?:smile:

 maxal 2006-12-01 20:48

There is a faster way to sieve out numbers of the form q*2^q+1 that are divisible by a given prime p>=3.

Suppose that q*2^q+1 is divisible by p. Then q*2^q = -1 (mod p) or alternatively q = - 2^(-q) (mod p).

Let q = -k (mod p-1) where 0 <= k < p-1, then q = - 2^(-q) = - 2^k (mod p).
From q = -k (mod p-1) and q = - 2^k (mod p) we can reconstruct q modulo p*(p-1) using Chinese theorem:
q = -k * p + 2^k * (p-1) (mod p*(p-1)) .............. (x)

In other words, for every k=0,...,p-2, there is an unique solution modulo p*(p-1) to the system of congruences
q*2^q + 1 = 0 (mod p)
q = -k (mod p-1)
and this solution is given by formula (x).

Therefore, sieving can be done as follows: for each prime p in selected range, let k go from 0 to p-2, compute
r = ((p-1-k) * p + (2^k mod p) * (p-1)) mod (p*(p-1)) (i.e., the smallest non-negative solution to (x)), and eliminate candidates
r, r + (p*(p-1)), r + 2*(p*(p-1)), ..., up to selected upper bound (for large p, it may appear that r is greater than the upper bound, in which case no actual elimination happens).

P.S. Of course, the powers (2^k mod p) can be computed incrementally as k goes from 0 to p-2:
having 2^k mod p=y computed, the value of 2^(k+1) mod p is computed as (y*2) mod p.

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.

 rogue 2006-12-01 21:42

I've looked at your post, i.e. Citrix's post, and see that he does use the same logic. I understand now why his code is more efficient. It is as he has stated. My code is tuned to sieving small ranges of consecutive n, which are fairly dense even after deep sieving. Since Citrix is using a large range of n where n must be prime, the density is much less (probably by a factor of between 20 and 30). The difference between our code would be even greater if his range were larger, but would be less if his range were smaller.

I could probably modify my code to use a dynamicly sized table (instead of a staticly sized table) to hold the values from 2^1 to 2^maxdiff (mod p). I suspect it would be much closer (and possibly faster) than Citrix's code. Citrix, if you are interested I could send you the source and point you to where the change needs to be made.

Maxal, I'll have to chew on your post a while. I think I have seen that suggestion before, but I didn't pursue it because as p gets large WRT the size of the range of n, it becomes much slower.

 Siemelink 2006-12-01 22:08

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 2006-12-01 23:58

[QUOTE=Siemelink;93004]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.[/QUOTE]

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 2006-12-02 05:04

[QUOTE=maxal;93001]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.[/QUOTE]
Correction: [b]r = ((z-k) * p + u[k] * (p-1)) mod (p*z)[/b]

 Citrix 2006-12-26 05:42

@ 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 2006-12-26 13:39

[QUOTE=Citrix;94763]@ 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)[/QUOTE]

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 2006-12-26 19:56

[QUOTE=rogue;94769]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.[/QUOTE]

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 2007-01-31 08:26

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

[URL="http://www.hoegge.dk/mersenne/cullenfactors.zip"]cullenfactors.zip[/URL] (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 [URL="http://www.prothsearch.net/cullenrange.html"]http://www.prothsearch.net/cullenrange.html[/URL] ) and n=5,000,000:

[URL="http://www.hoegge.dk/mersenne/cullen1.5M-5M.zip"]cullen1.5M-5M.zip[/URL]

 alpertron 2007-01-31 19:22

p*2[sup]p[/sup]+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[sup]p[/sup]+1 = 1*2[sup]2q+1[/sup]+1 = 2[sup]2q[/sup]*2+1 = (2[sup]2[/sup])[sup]q[/sup]*2+1 = 1[sup]q[/sup]*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[sup]p[/sup]+1 = (-2)*2[sup]p[/sup]+1 = -2[sup]p+1[/sup]+1 = -1+1 = 0 (mod p+2)

So in both cases p*2[sup]p[/sup]+1 is composite.

 brunoparga 2007-02-01 01:17

Dario,

Modular arithmetic still looks like a strange realm to me. So, I'm not sure if I understand what you've written:
[QUOTE=alpertron;97409]
p*2[sup]p[/sup]+1 = 1*2[sup]2q+1[/sup]+1 = 2[sup]2q[/sup]*2+1 = (2[sup]2[/sup])[sup]q[/sup]*2+1 = 1[sup]q[/sup]*2+1 = 2+1 = 0 (mod 3)
[/QUOTE]

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=alpertron;97409]p*2[sup]p[/sup]+1 = (-2)*2[sup]p[/sup]+1 = [B]-2[sup]p+1[/sup]+1 = -1+1[/B] = 0 (mod p+2)[/QUOTE]

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[sup]p+1[/sup] = -1 (mod p+2)

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

2[sup]p+1[/sup] = 1 (mod p+2)

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

Thanks a lot,
Bruno

 ATH 2007-02-01 03:59

[QUOTE=brunoparga;97434]
2[sup]p+1[/sup] = 1 (mod p+2)
[/QUOTE]

This is just [URL="http://primes.utm.edu/notes/proofs/FermatsLittleTheorem.html"]Fermat's Little Theorem[/URL] with p+2 = prime (p being twin prime) and a=2.

 alpertron 2007-02-01 12:14

[QUOTE=brunoparga;97434]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]
In that case p does not need to be prime. When p=1 (mod 3) the argument shown above demonstrates that p*2[sup]p[/sup]+1 is multiple of 3.

 AntonVrba 2007-02-23 10:46

This problem was topic at [URL="http://www.primepuzzles.net/problems/prob_050.htm"]www.primepuzzles.net[/URL] and a search has started for Cullen Primes but limited to prime exponents, see [URL="http://primepuzzles.redgolpe.com/topic.asp?TOPIC_ID=10"]primepuzzle forums[/URL]

 All times are UTC. The time now is 18:17.

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