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?

$\endgroup$
4
  • 8
    $\begingroup$ I suggest you check your program. $\endgroup$
    – Aryabhata
    Mar 14, 2012 at 21:35
  • 7
    $\begingroup$ By the way, $4\cdot 2^4-1=63$. $\endgroup$ Mar 14, 2012 at 21:39
  • $\begingroup$ @Josue Why didn't you try some values for yourself? You'd have had an answer right away! $\endgroup$
    – Pedro
    Mar 15, 2012 at 3:57
  • $\begingroup$ 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! $\endgroup$
    – wjmolina
    Mar 15, 2012 at 6:47

6 Answers 6

13
$\begingroup$

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

$\endgroup$
1
  • 2
    $\begingroup$ That is, for 94 out of 100 possible values of $1\leq n\leq 100$, the quantity $n2^n-1$ is not prime. $\endgroup$ Mar 14, 2012 at 22:58
11
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ That's interesting! I just found out that $n\cdot2^n+1$ are called Cullen numbers. o.o $\endgroup$
    – wjmolina
    Mar 14, 2012 at 21:52
  • $\begingroup$ Wow! oeis.org looks like a legacy archive, but indeed is useful collection $\endgroup$ Mar 14, 2012 at 22:32
  • $\begingroup$ Why do you call it "legacy"? $\endgroup$ Mar 14, 2012 at 23:42
  • $\begingroup$ Looks old style (so my remark was for the appearance - sorry if I confused with that remark) $\endgroup$ Mar 15, 2012 at 1:11
7
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ $4 \times 2^4 - 1 = 63$ $\endgroup$
    – user17762
    Mar 14, 2012 at 21:36
  • $\begingroup$ @SivaramAmbikasaran: True :-) I started with trying to find one divisibly by $5$ for some reason. $\endgroup$
    – Aryabhata
    Mar 14, 2012 at 21:37
  • $\begingroup$ That's interesting. I must've messed up my programming. Thanks for the counterexample. $\endgroup$
    – wjmolina
    Mar 14, 2012 at 21:38
3
$\begingroup$

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

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .