4

While writing an answer to an unrelated question, I stumbled onto a curious fact that I hadn't noticed before: the binary expansion of $x = k(2^n-1)$, for all non-negative integers $n$ and all integers $1 ≤ k ≤ 2^n$, has exactly $n$ bits set (i.e. the Hamming weight of $x$ written in binary is $n$; or, in other words, $x$ is the sum of exactly $n$ distinct non-negative integer powers of two).

For example, for $n = 4$, we have:

$$\begin{array}{rcrcrcl} 1 \times (2^4-1) &=& 15 &=& 0000\,1111_2 &=& 2^3 + 2^2 + 2^1 + 2^0 \\ 2 \times (2^4-1) &=& 30 &=& 0001\,1110_2 &=& 2^4 + 2^3 + 2^2 + 2^1 \\ 3 \times (2^4-1) &=& 45 &=& 0010\,1101_2 &=& 2^5 + 2^3 + 2^2 + 2^0 \\ 4 \times (2^4-1) &=& 60 &=& 0011\,1100_2 &=& 2^5 + 2^4 + 2^3 + 2^2 \\ 5 \times (2^4-1) &=& 75 &=& 0100\,1011_2 &=& 2^6 + 2^3 + 2^1 + 2^0 \\ 6 \times (2^4-1) &=& 90 &=& 0101\,1010_2 &=& 2^6 + 2^4 + 2^3 + 2^1 \\ 7 \times (2^4-1) &=& 105 &=& 0110\,1001_2 &=& 2^6 + 2^5 + 2^3 + 2^0 \\ 8 \times (2^4-1) &=& 120 &=& 0111\,1000_2 &=& 2^6 + 2^5 + 2^4 + 2^3 \\ 9 \times (2^4-1) &=& 135 &=& 1000\,0111_2 &=& 2^7 + 2^2 + 2^1 + 2^0 \\ 10 \times (2^4-1) &=& 150 &=& 1001\,0110_2 &=& 2^7 + 2^4 + 2^2 + 2^1 \\ 11 \times (2^4-1) &=& 165 &=& 1010\,0101_2 &=& 2^7 + 2^5 + 2^2 + 2^0 \\ 12 \times (2^4-1) &=& 180 &=& 1011\,0100_2 &=& 2^7 + 2^5 + 2^4 + 2^2 \\ 13 \times (2^4-1) &=& 195 &=& 1100\,0011_2 &=& 2^7 + 2^6 + 2^1 + 2^0 \\ 14 \times (2^4-1) &=& 210 &=& 1101\,0010_2 &=& 2^7 + 2^6 + 2^4 + 2^1 \\ 15 \times (2^4-1) &=& 225 &=& 1110\,0001_2 &=& 2^7 + 2^6 + 2^5 + 2^0 \\ 16 \times (2^4-1) &=& 240 &=& 1111\,0000_2 &=& 2^7 + 2^6 + 2^5 + 2^4 \\ \end{array}$$

The pattern breaks at $k=17$, where $17 \times 15 = 255 = 1111\,1111_2$. (This is not surprising; indeed, it's easy to see that the binary expansion of $(2^n+1)(2^n-1) = 2^{2n}-1$ will always have $2n > n$ bits set.) But it's remarkable that it does seem to hold for all $1 ≤ k ≤ 2^n$ and for all $n ≥ 0$.

But how to prove that it does?

I tried to look for an existing proof on math.SE, but all I found (perhaps because I was having trouble finding good search keywords) was this Q&A about showing that the binary expansion of $k(2^n-1)$ has at least $n$ bits set for all $k$, so I figured I'd ask a new question (and try to answer it myself).

Ilmari Karonen
  • 26,117
  • 1
    Does this answer your question? Binary Multiplication Counting Ones – Sil Aug 22 '22 at 12:05
  • @Sil: It does indeed! Hmm… I'm a bit hesitant to just close my question as a duplicate, since the older one doesn't seem as clear (although that could be just me being biased) and is really two questions in one. But this is indeed a dupe. – Ilmari Karonen Aug 22 '22 at 12:09
  • 1
    It would seem a shame to lose the answer you wrote, including the observation about the ones' complement. If you decide to delete the question, at least post your answer as an answer to the other question. – David K Aug 22 '22 at 12:29

1 Answers1

4

Note that $k(2^n-1) = k2^n - k = (k - 1)2^n + (2^n - k)$.

Since $1 ≤ k ≤ 2^n$, it follows that $0 ≤ 2^n - k < 2^n$, so the binary expansion of $2^n - k$ is at most $n$ bits long. Meanwhile, the binary expansion of $(k - 1)2^n$ is the same as that of $k-1$, but with $n$ zero bits appended to the right.

Thus, when $k(2^n-1)$ is written out as a $2n$ bit binary number, the leftmost $n$ bits of it will be identical to those of $k - 1$, while the rightmost $n$ bits are identical to those of $2^n - k$.

It remains to be shown that the binary expansions of $k - 1$ and $2^n - k$ together always have exactly $n$ bits set. But that's indeed always the case, since $2^n - k = (2^n - 1) - (k - 1)$ is the $n$-bit ones' complement of $k - 1$, and thus has exactly those bits set in its binary expansion that are not set in the binary expansion of $k - 1$.

Ilmari Karonen
  • 26,117