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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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