Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I ran into the following sequence:

$$f_n=n\cdot2^n-1.$$

Apparently, for $n>1$, $f_n$ will yield a prime number. It will not list all of them, however.

My question is: Is this true for all $n$?

I currently have a program running that has thus far checked that it is true for all $n\leq49$. What do you guys think?

share|improve this question
8  
I suggest you check your program. –  Aryabhata Mar 14 '12 at 21:35
7  
By the way, $4\cdot 2^4-1=63$. –  André Nicolas Mar 14 '12 at 21:39
    
@Josue Why didn't you try some values for yourself? You'd have had an answer right away! –  Pedro Tamaroff Mar 15 '12 at 3:57
    
I agree, and I apologize for not having done that to begin with. :/ I guess I just have this thing for programming where, in my excitement, I do it blindly and without much prior thought. I checked its validity by hand for the first two cases or so, and upon seeing that it worked, I jumped straight into the coding... had I done just one more number! –  Josué Molina Mar 15 '12 at 6:47
add comment

6 Answers 6

up vote 12 down vote accepted

Here is a list of numbers $1\leq n\leq 100$ for which $n2^n-1$ is not prime:

$$1,4, 5, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24,$$ $$ 25, 26, 27, 28, 29, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45,$$ $$46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65,$$ $$66, 67, 68, 69, 70, 71, 72, 73, 74, 76, 77, 78, 79, 80, 82, 83, 84, 85, 86, 87,$$ $$88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100.$$

share|improve this answer
2  
That is, for 94 out of 100 possible values of $1\leq n\leq 100$, the quantity $n2^n-1$ is not prime. –  Álvaro Lozano-Robledo Mar 14 '12 at 22:58
add comment

These are called Woodall numbers. See https://oeis.org/A002234 and references given there. It is conjectured that infinitely many Woodall numbers are prime, but this is still very much an open question.

share|improve this answer
1  
That's interesting! I just found out that $n\cdot2^n+1$ are called Cullen numbers. o.o –  Josué Molina Mar 14 '12 at 21:52
    
Wow! oeis.org looks like a legacy archive, but indeed is useful collection –  Kirthi Raman Mar 14 '12 at 22:32
    
Why do you call it "legacy"? –  Robert Israel Mar 14 '12 at 23:42
    
Looks old style (so my remark was for the appearance - sorry if I confused with that remark) –  Kirthi Raman Mar 15 '12 at 1:11
add comment

Your program apparently needs work. Let $n=2^{2k}$. Then $f_n=2^{2k}\times2^{2^{2k}}-1=2^{2k+2^{2k}}-1=(2^{k+2^{2k-1}}+1)(2^{k+2^{2k-1}}-1)$.

So $f_n$ is composite for all positive integer powers of 4.

share|improve this answer
add comment

$16\times 2^{16}-1$ is divisible by $5$.

This is because $2^4 = 16 = 1 \mod 5$.

In general, for every odd prime $p$, for $n = (p-1)^2, \ n2^n - 1$ is divisible by $p$.

share|improve this answer
1  
$4 \times 2^4 - 1 = 63$ –  user17762 Mar 14 '12 at 21:36
    
@SivaramAmbikasaran: True :-) I started with trying to find one divisibly by $5$ for some reason. –  Aryabhata Mar 14 '12 at 21:37
    
That's interesting. I must've messed up my programming. Thanks for the counterexample. –  Josué Molina Mar 14 '12 at 21:38
add comment

$n = 4$ is the first value for which $f_n$ isn't prime.

$4 \times 2^4 - 1 = 63 = 3^2 \times 7$

share|improve this answer
add comment

Notice that if $n = 2^{2a}$ for some positive integer $a,$ then $n2^{n}- 1$ is never prime, because $n 2^{n}-1 = 2^{ 2a+2^{2a}} -1,$ which is divisible by $3$ as $2^{2m}-1$ is divisible by $3$ for any positive integer $m.$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.