Problems & Puzzles:
Problems
Problem 50.
Is there
a Cullen prime C_{n }with n prime ?
Patrick Capelle sent the
following problem for our pages:
The context :
C_{n }= n*2^{n}+1 are called Cullen
numbers.
W_{n} = n*2^{n}1 are called Woodall numbers.
There are Woodall primes W_{n} with n prime.
Examples : n = 3, 751, 12379.
See
http://www.prothsearch.net/woodall.html
But what about the Cullen primes ?
Questions :
1. Is there a Cullen prime C_{n }
with n prime ?
2. Are there arguments against the
existence of such a Cullen prime ?
____
References :
http://mathworld.wolfram.com/CullenNumber.html
http://primes.utm.edu/glossary/page.php?sort=Cullens
http://primes.utm.edu/top20/page.php?id=6
http://www.prothsearch.net/cullen.html
Contributions came from Daniele Degiorgi, Enoch Haga &
Farideh Firoozbakht.
***
Daniele wrote:
May be it is
unrelated, but I noted that for some primes p C_p has a common
factor with p+2.
For example
C_3=25 is multiple of 5, C_13 is divisible by 3 like 15, and C_47 is
divisible by 7 like 49.
Within the
first 50 primes, only for p = 53, 113 and 233 p+2 is relatively
prime with C_p. In this case, the smaller divisor of C_p are
respectively 5591, 241 and 17389.
Anyway, for
all 10000 odd primes p < 104743 there are only 1879 for which C_p
is prime with p+2 and for each p such that p+2 is multiple of 3,
C_p is also multiple of 3.
The latter
property, i.e. If p is of the form 3k2, then C_p is divisible by 3
Should be
easy to prove just using the little Fermat theorem
Enoch wrote:
As you note, this subject is covered in Ribenboim, The
New Book of Prime
Number Records, pp 360361. He has an apparent typo, 5611 rather than
the
correct 6611... Hooley in 1976 gave a formula for the number of Cullen
numbers <= x which are prime (page 361)... Hooley's formula implies an
infinite number of Cullen primes. The question is open.
***
Farideh wrote:
For many kind of primes p we can prove that C_p is
composite.
Some of them are as follows.
1. If both numbers p & p+2 are prime then p+2
divides C_p, so C_p is
composite.
Proof :
C_p = p*2^p + 1 = ((p+2)2)*2^p + 1 = (p+2)*2^p  (2^(p+1) 1)
and since (p+2) is an odd prime by FLT (Ferrmat's
Little Theorem) p+2
divides 2^(p+1) 1. So p+2 divides (p+2)*2^p 
(2^(p+1) 1) = C_p.
2. we know if p > 3 is prime then p is of the
form 6k1 or 6k+1,
for the second case C_p is composite because 3
divides C_p.
Proof : p
= 6k+1, C_p = (6k+1)*2^(6k+1)+1 so, C_p = 1*(1)^(6k+1)+1 = 0
(mod 3)hence 3 divides C_p.
3. If p is of the form 6k1 and k = 3 (mod 10) or
k = 4 (mod 10) then 5 divides C_p,
so C_p is composite.
Proof :
p = 6k1, C_p = (6k1)*2^(6k1)+1
Case 1. k = 3 (mod 10); k = 10m+3; C_p =
(6(10m+3)1)*2^(6(10m+3)1)+1,
hence,
C_p = (60m+17)*2^(60m+17)+1
= (60m+15+2)*2^(60m+16+1)+1
= (60m+15+2)*4^(30m+8)*2+1
so, C_p = 2*(1)^(30m+8)*2+1 = 2*1*2+1= 0 (mod
5) or 5 divides C_p.
Case 2. k = 4 (mod 10); k = 10m+4; C_p =
(6(10m+4)1)*2^(6(10m+4)1)+1,
hence,
C_p = (60m+23)*2^(60m+23)+1
= (60m+20+3)*2^(60m+22+1)+1
= (60m+20+3)*4^(30m+11)*2+1
so, C_p = 3*(1)^(30m+11)*2+1 =3*(1)*2+1 =
0 (mod 5) or 5 divides C_p.
The proofs of the following cases are easy
and similar to Number 3.
4. If p is of the form 6k1 and k = 1 (mod 7)
then 7 divides C_p.
5. If p is of the form 6k1 and k = i (mod
5*11) where i is in the set {8,12, 20, 26, 54}
"6. If p is of the form 6k1
and k = i (mod 4*13) where i is in the set
{2, 7, 28, 33} then 13 divides C_p."
7. If p is of the form 6k1 and k = i (mod
4*17) where i is in the set {13, 26, 27, 48}
then 17 divides C_p.
8. If p is of the form 6k1 and k =
i (mod 3*19) where i is in the set {3, 20, 25} then
19 divides C_p.
9. If p is of the form 6k1 and k = i (mod
11*23) where i is in the set {1, 14, 18, 21, 46,
48, 72, 88, 107, 170, 218} then
23 divides C_p.
10, If p is of the form 6k1 and k =
i (mod 14*29) where i is in the set {16, 23, 31, 66,
71, 75, 138, 140, 165, 189, 293, 316,
384, 396} then 29 divides C_p.
...
And finally it seems that we can say,
For each prime q, q > 3, there
exist a number j(q) and a nonempty set
A(q) where j(q) divides q1 and
A(q) is a subset of {1, 2, 3, ..., j(q)*q1}
such that If p is of the form
6k1 and k = i (mod j(q)*q) where i is in the
set A(q) then q divides C_p.
Later she added:
I have found the following other cases that C_n is
composite, but for
some of these cases n is composite. The proofs of
all of them are easy.
1. If n+1 is an odd prime then n+1 divides C_n,
so C_n is composite.
Numbers n such that both numbers n+1 & C_n/(n+1)
are prime:
2, 4, 16, 5692, ...
2. If n+2 is an odd prime then n+2 divides C_n,
so C_n is composite.
(In my previous email I wrote the special
case that n is also a prime.)
Numbers n such that both numbers n+2 & C_n/(n+2) are
prime:
3, 5, 9, 11, 21, 35, 101, 165, 191, 459, 671,
...
3. If 2n1 is prime and 4  (n2)(n3) , namely n =
2 (mod 4) or n = 3 (mod 4)
then 2n1 divides C_n, so C_n is composite.
Numbers n such that both numbers n+2 & C_n/(n+2) are
prime: 2, 3, ....
4. If (2n+1)/3 is prime and 4  (n1)(n2) , namely
n = 1 (mod 4) or n = 2 (mod 4)
then (2n+1)/3 divides C_n, so C_n is composite.
5. If n/2+2 is prime then n/2+2 divides C_n, so C_n
is composite.
6. If 6  (n1)(n2) , namely n = 1 (mod 6) or n
= 2 (mod 6) then 3 divides
C_n, so C_n is composite.
(In my previous email I wrote the special
case that n is also a prime.)
Numbers n such that 1/3*C_n is prime: 2, 8,
158, 2150, 3698, 8330, ...
***
n = 6 is an interesting example for the
three cases 1, 3 & 5:
6+1 = 7 is an odd prime so 7
divides C_6,
6/2+2 = 5 is prime so 5
divides C_6,
2*61 = 11 is prime and 6 = 2 (mod 4) so 11
divides C_6,
***
Anton Vrba added:
