20061124, 21:03  #1 
Jun 2003
1,553 Posts 
Cullen prime problem (How everything began)
On http://primes.utm.edu/top20/page.php?id=6
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! Last fiddled with by hhh on 20070324 at 23:21 
20061124, 21:15  #2 
Feb 2004
France
911 Posts 
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:Cullen Primes it is said that the new and biggest one is: 1354828*2^1354828+1 . T. 
20061124, 21:30  #3  
"Sander"
Oct 2002
52.345322,5.52471
29×41 Posts 
Quote:
Last fiddled with by smh on 20061124 at 21:30 

20061124, 21:37  #4 
Feb 2004
France
911 Posts 

20061124, 22:57  #5 
Jun 2003
1,553 Posts 

20061125, 01:27  #6  
"Mark"
Apr 2003
Between here and the
5,801 Posts 
Quote:


20061125, 05:55  #7  
Jun 2003
1,553 Posts 
Quote:
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! 

20061125, 19:58  #8  
"Mark"
Apr 2003
Between here and the
5,801 Posts 
Quote:


20061128, 22:57  #9 
Jun 2003
611_{16} Posts 
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? 
20061201, 20:48  #10 
Feb 2005
2^{2}·3^{2}·7 Posts 
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 p1) where 0 <= k < p1, then q =  2^(q) =  2^k (mod p). From q = k (mod p1) and q =  2^k (mod p) we can reconstruct q modulo p*(p1) using Chinese theorem: q = k * p + 2^k * (p1) (mod p*(p1)) .............. (x) In other words, for every k=0,...,p2, there is an unique solution modulo p*(p1) to the system of congruences q*2^q + 1 = 0 (mod p) q = k (mod p1) 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 p2, compute r = ((p1k) * p + (2^k mod p) * (p1)) mod (p*(p1)) (i.e., the smallest nonnegative solution to (x)), and eliminate candidates r, r + (p*(p1)), r + 2*(p*(p1)), ..., 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 p2: 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 p1 with the multiplicative order of 2 modulo p (that is a divisor of p1). So, instead of letting k go from 0 to p2, 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 z1, compute r = ((zk) * p + u[k] * z) mod (p*z), and eliminate candidates r, r + (p*z), r + 2*(p*z), ..., up to selected upper bound. Last fiddled with by maxal on 20061201 at 21:11 
20061201, 21:42  #11 
"Mark"
Apr 2003
Between here and the
5,801 Posts 
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. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Generalized Cullen and Woodall Searches  rogue  And now for something completely different  29  20191120 14:01 
Cullen and Woodall altering on Prime Pages  jasong  jasong  9  20080125 01:51 
Can we add Cullen and Woodall p1ing here?  jasong  Marin's Mersennearies  1  20071118 23:17 
Prime Cullen Prime, Rest in Peace  hhh  Prime Cullen Prime  4  20070921 16:34 
Smallest floor of k for cullen prime  Citrix  Prime Cullen Prime  12  20070426 19:52 