How to check if an integer can be represented with all set bits for any given base?

70 Views Asked by At

By all set bits, I mean all the set bits are placed consecutively together. e.g., for base 2, we have 1, 3, 7, 15, 31, 63, i.e., any integer $x$ such that $x = 2^m - 1$ for some integer $m$.

In binary, $1$ is $1$ and $3$ is $11$ and $7$ is $111$ and $15$ is $1111$ and so on.

I want to be able to do this with any base. Based on wolfram, I am inducing that the formula for checking an integer $x$ and some base $b$ and some non-negative exponent $m$ is

$$ x = \frac{1}{b - 1}\left(b^m - 1 \right) $$

How can you intuitively derive this formula?


After I wrote out $x = b^0 + b^1 + b^2 + \ldots + b^m$, it became obvious to me how to derive this expression.

Let $f(m) = x = b^0 + b^1 + b^2 + \ldots + b^m$, then we have $$ f(m) / b = 1/b + b^0 + b^1 + \ldots + b^{m - 1} \\ = 1/b + f(m) - b^m \\ \implies f(m) = 1 + bf(m) - b^{m + 1} \\ \therefore f(m) = \frac{b^{m + 1} - 1}{b - 1} $$

2

There are 2 best solutions below

0
On

Your formula for $x$ is a geometric sum of $m$ digits of all $1$s,

$$ {\overbrace{111\cdots1}^m}_b = b^0+b^1+\cdots + b^{m-1} = \frac{b^m-1}{b-1} = \frac{10_b^m-1}{10_b-1}$$

To apply the usual proof of geometric sum specifically to $x$ in base $b$,

$$\begin{array}{crcrl} &10_b x &= &{\overbrace{111\ldots 1}^m0}_b\\ -& x &= &{\overbrace{11\ldots 11}^m}_b\\ \hline &(10_b-1)x &= &1{\overbrace{00\ldots00}^m}_b & -1\\ &&= &10^m_b&-1\\ \hline &x &= &\dfrac{10^m_b-1}{10_b-1} \end{array}$$

0
On

I don't know if you'll find this intuitive, but it may, at least, make the result more memorable. First note that your number $x$ with $m$ bits "set" is $x = b^{m-1} + b^{m - 2} + \ldots + b + 1$. Then lay out the calculation of $(b- 1)x$ like this: $$ \begin{align*} (b - 1)(b^{m-1} + b^{m - 2} + \ldots + b + 1) &= \begin{array}[t]{ccccccc} b^m &+b^{m-1} &+ &\ldots &+ b^2 &+ b\\ &-b^{m-1} &- &\ldots &- b^2 &- b &- 1 \end{array}\\ &= b^m - 1 \end{align*} $$ Now divide both sides by $b - 1$. This is how I remember the formula for the sum of a geometric progression.