# Prime Number Generator: $n\cdot2^n - 1$?

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?

-
I suggest you check your program. –  Aryabhata Mar 14 '12 at 21:35
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é Mar 15 '12 at 6:47

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

-
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

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.

-
That's interesting! I just found out that $n\cdot2^n+1$ are called Cullen numbers. o.o –  Josué 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

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.

-

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

-
$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é Mar 14 '12 at 21:38

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

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

-

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

-