Solve $\log_2(x+1)=⌊\log_2(x)⌋+1$ in positive integers

93 Views Asked by At

This question is related to: Find all positive integer solutions verifying two conditions

Let us consider the following equation: $$\log_2(x+1)=⌊\log_2(x)⌋+1$$ $\log_2$ is the logarithm in base $2$ (https://www.vedantu.com/maths/log-base-2) and $⌊.⌋$ is the integer part. I am asking on how one can find all the integer solutions $x$. One solution is when $x=3$. Probably, the equation has no solutions for some $x>a$ with $a$ is a given constant.

1

There are 1 best solutions below

3
On BEST ANSWER

In

$$\log_2(x+1)=⌊\log_2(x)⌋+1\tag 1$$ the right side is an integer, thus $x+1$ must be an integer power of $2$. Hence $x+1=2^n$ with $n\in\Bbb Z$. In addition, we have that $x$ must be positive (otherwise the $\log$ on the right side is not defined):

$$x=2^n-1 > 0 \iff x+1= 2^n > 1 \implies n > 0 = \log_2 1 $$ so that $n\geqslant1$.

To see that all such $x=2^n-1$ are solutions of $(1)$, observe that $1+⌊\log_B m⌋$ is the number of digits needed to represent $m\in\Bbb N$ in base $B$. In base $2$, $x$ has the representation

$$x=2^n-1 = \underbrace{1\cdots1}_{n\text{ times}}\tag 2$$

so that $⌊\log_2 x⌋+1 = n$. On the other hand we have that $\log_2 (x+1) = \log_2(2^n) = n$ and $(1)$ holds for all $x=2^n-1$ with $n\in\Bbb N$.


A more rigoros treatment of the right-hand side of $(1)$ follows: As $\log_2$ is strictly increasing, we have

$$\log_2 x = \log_2(2^n-1) < \log_2(2^n) = n \tag 3$$

so that $\log_2 x$ is strictly smaller than integer $n$ and hence $⌊\log_2 x⌋<n$. On the other hand:

$$\log_2 x = \log_2(2^n-1) \geqslant \log_2(2^{n-1}) = n-1 \tag4$$ where the inequality holds due to $2^n-1\geqslant 2^{n-1}$ as $n\geqslant1$. Equation $(4)$ therefore implies $⌊\log_2 x⌋\geqslant n-1$. Taking the two estimates together:

$$n-1\leqslant ⌊\log_2 x⌋ < n \implies ⌊\log_2 x⌋ =n-1 \implies 1 +⌊\log_2 x⌋ = n$$ so that the RHS and the LHS of $(1)$ are equal to $n$ for all $n\in\Bbb N$.


Oops, I just saw that you are looking only for positive integer solutions anyway, so some of the reasoning from above can be omitted.