1
$\begingroup$

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?

  • 0
    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!2012-03-15

6 Answers 6

13

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

  • 2
    That is, for 94 out of 100 possible values of $1\leq n\leq 100$, the quantity $n2^n-1$ is not prime.2012-03-14
11

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.

  • 0
    Looks old style (so my remark was for the appearance - sorry if I confused with that remark)2012-03-15
7

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.

5

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

  • 0
    That's interesting. I must've messed up my programming. Thanks for the counterexample.2012-03-14
3

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

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

2

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