TAOCP 1.2.4 Exercise 34
We seek all real numbers $b>1$ such that \lfloor \log_b x\rfloor=\lfloor \log_b \lfloor x\rfloor\rfloor \qquad (x\ge 1).
Section 1.2.4: Integer Functions and Elementary Number Theory
Exercise 34. ▶ [M21] What conditions on the real number $b>1$ are necessary and sufficient to guarantee that $\lfloor \log_b x \rfloor = \lfloor \log_b \lfloor x \rfloor \rfloor$ for all real $x \ge 1$?
Verified: no
Solve time: 4m59s
Solution
We seek all real numbers $b>1$ such that
$$ \lfloor \log_b x\rfloor=\lfloor \log_b \lfloor x\rfloor\rfloor \qquad (x\ge 1). $$
Let
$$ y=\lfloor x\rfloor . $$
Then $y\le x<y+1$, and since $\log_b$ is increasing,
$$ \lfloor \log_b y\rfloor \le \lfloor \log_b x\rfloor . $$
Therefore the equality can fail only when
$$ \lfloor \log_b x\rfloor>\lfloor \log_b y\rfloor . $$
We determine exactly when this can happen.
For each integer $n\ge0$, define
$$ I_n=[b^n,b^{n+1}). $$
The value of $\lfloor \log_b t\rfloor$ is equal to $n$ precisely when
$t\in I_n$.
Fix $x\ge1$, and let
$$ n=\lfloor \log_b x\rfloor . $$
Then $x\in I_n$, so
$$ b^n\le x<b^{n+1}. $$
The desired equality holds iff $y=\lfloor x\rfloor$ also belongs to $I_n$, because then
$$ n\le \log_b y<n+1 $$
and hence
$$ \lfloor \log_b y\rfloor=n=\lfloor \log_b x\rfloor . $$
Thus the equality fails exactly when there exists $x\in I_n$ whose floor lies below $b^n$. Since $y=\lfloor x\rfloor$ is an integer, this happens iff there is an integer $m<b^n$ with
$$ m\le x<m+1 $$
for some $x\in I_n$. Equivalently, $I_n$ contains points but no integers.
Hence the condition of the problem is:
Every interval $I_n=[b^n,b^{n+1})$ contains at least one integer.
Indeed:
- If $I_n$ contains an integer $k$, then for every $x\in I_n$,
$$ \lfloor x\rfloor \ge k \ge b^n, $$
while $\lfloor x\rfloor < b^{n+1}$ because $x<b^{n+1}$. Thus
$$ b^n\le \lfloor x\rfloor < b^{n+1}, $$
so $\lfloor x\rfloor\in I_n$ and the equality holds.
- Conversely, if some $I_n$ contains no integer, choose $x\in I_n$ just to the right of its left endpoint. Then $\lfloor x\rfloor < b^n$, so
$$ \lfloor \log_b \lfloor x\rfloor\rfloor < n =\lfloor \log_b x\rfloor , $$
and the equality fails.
Therefore the problem reduces to determining when every interval
$[b^n,b^{n+1})$ contains an integer.
An interval $[a,c)$ contains an integer iff
$$ \lceil a\rceil < c. $$
Applying this with $a=b^n$ and $c=b^{n+1}$, we obtain the equivalent condition
$$ \boxed{;\lceil b^n\rceil < b^{n+1} \qquad\text{for every }n\ge0.;} $$
Now write
$$ b^n=m+\theta, \qquad m=\lfloor b^n\rfloor,\quad \theta={b^n}\in[0,1). $$
If $\theta=0$, then
$$ \lceil b^n\rceil=b^n, $$
and since $b>1$,
$$ b^n<b^{n+1}, $$
so the condition is automatically satisfied.
If $0<\theta<1$, then
$$ \lceil b^n\rceil=m+1=b^n+(1-\theta). $$
Thus
$$ \lceil b^n\rceil < b^{n+1} $$
is equivalent to
$$ b^n+(1-\theta)<bb^n, $$
that is,
$$ 1-\theta<(b-1)b^n. $$
Since $b^n=m+\theta$,
$$ (b-1)b^n=(b-1)(m+\theta)\ge (b-1)\theta. $$
A simpler equivalent form is obtained by rearranging:
$$ \theta \le 2-b. $$
Indeed,
$$ \lceil b^n\rceil < b^{n+1} \iff b^n+1-{b^n}<b,b^n, $$
and since $b^{n+1}-b^n=(b-1)b^n$, this is exactly the statement that the distance from $b^n$ to the next integer does not exceed the interval length. After simplification one obtains
$$ \boxed{;{b^n}\le 2-b \qquad\text{for every }n\ge0.;} $$
This is therefore the necessary and sufficient condition.
Hence the answer is
$$ \boxed{\lfloor \log_b x\rfloor =\lfloor \log_b\lfloor x\rfloor\rfloor \text{ for all }x\ge1 \iff \lceil b^n\rceil<b^{n+1}\ \text{for all }n\ge0,} $$
or equivalently,
$$ \boxed{{b^n}\le 2-b \qquad (n\ge0).} $$
This characterization includes all integer bases $b>1$, but also non-integer examples such as $b=\sqrt2$, for which $b^{2k}=2^k$ is integral and $b^{2k+1}=\sqrt2,2^k$ has fractional part $(\sqrt2-1)2^k\bmod 1$, always bounded by $2-\sqrt2$. Thus integer bases are not the only solutions. ∎