TAOCP 4.4 Exercise 9
We are asked to find, for each nonnegative integer $k$, the smallest nonnegative integer $u$ such that \left\lfloor \frac{v_k(u)}{16} \right\rfloor \ne \left\lfloor \frac{u}{10} \right\rfloor, where
Exercise 9. ▶ [M29] The purpose of this exercise is to compute $\lfloor u/10 \rfloor$ with binary shifting and addition operations only, when $u$ is a nonnegative integer. Let $v_0(u) = 3\lfloor u/2 \rfloor + 3$ and
$$v_{k+1}(u) = v_k(u) + \lfloor v_k(u)/2^{k+2} \rfloor \quad \text{for } k \ge 0.$$
Given $k$, what is the smallest nonnegative integer $u$ such that $\lfloor v_k(u)/16 \rfloor \ne \lfloor u/10 \rfloor$?
Verified: no
Solve time: 8m55s
Exercise 4.4.9 [M29]
We are asked to find, for each nonnegative integer $k$, the smallest nonnegative integer $u$ such that
$$ \left\lfloor \frac{v_k(u)}{16} \right\rfloor \ne \left\lfloor \frac{u}{10} \right\rfloor, $$
where
$$ v_0(u) = 3 \lfloor u/2 \rfloor + 3, \qquad v_{k+1}(u) = v_k(u) + \left\lfloor \frac{v_k(u)}{2^{k+2}} \right\rfloor \text{ for } k\ge0. $$
We proceed case by case, carefully establishing minimality.
Case $k=0$
We have
$$ v_0(u) = 3 \lfloor u/2 \rfloor + 3. $$
Write $u = 10q + r$ with $0 \le r \le 9$. Then
$$ \lfloor u/2 \rfloor = \lfloor (10q+r)/2 \rfloor = 5q + \lfloor r/2 \rfloor, $$
so
$$ v_0(u) = 15q + 3 \lfloor r/2 \rfloor + 3. $$
Since $0 \le \lfloor r/2 \rfloor \le 4$, we have
$$ 15q + 3 \le v_0(u) \le 15q + 15. $$
Dividing by 16 and taking the floor gives
$$ \left\lfloor \frac{v_0(u)}{16} \right\rfloor = \begin{cases} q, & 15q + 15 < 16(q+1) \implies q \le 3, \ \text{possibly } q+1, & q=3 \text{ if } v_0(u) \ge 16 \cdot 4 = 64. \end{cases} $$
Compute the threshold explicitly:
$$ v_0(u) \ge 16(q+1) \implies 15q + 3 \lfloor r/2 \rfloor + 3 \ge 16(q+1) \implies 3 \lfloor r/2 \rfloor \ge q + 13. $$
For $q=3$, this requires $3 \lfloor r/2 \rfloor \ge 16 \implies \lfloor r/2 \rfloor \ge 6$, which is impossible ($\lfloor r/2 \rfloor \le 4$). Hence for $q=3$ we still have $\lfloor v_0(u)/16 \rfloor = 3$.
Check $q=4$ ($u=40$ to 49):
$$ v_0(40) = 3 \lfloor 40/2 \rfloor + 3 = 3 \cdot 20 + 3 = 63, \quad \lfloor 63/16 \rfloor = 3, $$
but $\lfloor 40/10 \rfloor = 4$.
Thus the minimal counterexample is
$$ \boxed{u=40}. $$
Minimality: any $u<40$ has $q \le 3$, so $\lfloor v_0(u)/16 \rfloor = q = \lfloor u/10 \rfloor$. Hence $u=40$ is indeed minimal.
Case $k=1$
We have
$$ v_1(u) = v_0(u) + \left\lfloor \frac{v_0(u)}{4} \right\rfloor. $$
Compute $v_0(u)$ for small $u$:
$$ \begin{aligned} v_0(0)=3,&\quad v_0(1)=3,\ v_0(2)=6,&\quad v_0(3)=6,\ v_0(4)=9,&\quad v_0(5)=9,\ v_0(6)=12,&\quad v_0(7)=12,\ v_0(8)=15,&\quad v_0(9)=15. \end{aligned} $$
Then
$$ v_1(u) = v_0(u) + \lfloor v_0(u)/4 \rfloor: $$
$$ \begin{aligned} v_1(0) = 3 + 0 = 3,&\quad v_1(1) = 3,\ v_1(2) = 6+1=7,&\quad v_1(3)=7,\ v_1(4)=9+2=11,&\quad v_1(5)=11,\ v_1(6)=12+3=15,&\quad v_1(7)=15,\ v_1(8)=15+3=18,&\quad v_1(9)=18. \end{aligned} $$
Divide by 16:
$$ \lfloor v_1(u)/16 \rfloor = \begin{cases} 0,& 0 \le u \le 7,\ 1,& u=8,9. \end{cases} $$
Meanwhile $\lfloor u/10 \rfloor = 0$ for $0 \le u \le 9$.
Hence the first counterexample occurs at
$$ \boxed{u=8}. $$
Minimality: $u<8$ gives $\lfloor v_1(u)/16 \rfloor = 0 = \lfloor u/10 \rfloor$. Therefore $u=8$ is minimal.
Case $k \ge 2$
We proceed recursively and examine small $u$. First compute $v_2(u)$ explicitly for $u=0,1,2,3,4,5,6$.
We have
$$ v_2(u) = v_1(u) + \left\lfloor \frac{v_1(u)}{8} \right\rfloor. $$
From above:
$$ \begin{aligned} v_2(0) &= 3 + \lfloor 3/8 \rfloor = 3,\ v_2(1) &= 3,\ v_2(2) &= 7 + \lfloor 7/8 \rfloor = 7,\ v_2(3) &= 7,\ v_2(4) &= 11 + \lfloor 11/8 \rfloor = 11 + 1 = 12,\ v_2(5) &= 11 + \lfloor 11/8 \rfloor = 12,\ v_2(6) &= 15 + \lfloor 15/8 \rfloor = 15 + 1 = 16. \end{aligned} $$
Divide by 16:
$$ \lfloor v_2(u)/16 \rfloor = \begin{cases} 0,& 0 \le u \le 5,\ 1,& u=6. \end{cases} $$
Meanwhile $\lfloor u/10 \rfloor = 0$ for $0 \le u \le 9$.
Hence the minimal counterexample for $k=2$ is
$$ u=6. $$
Induction for $k \ge 2$
Assume $k \ge 2$. We prove by induction that $u=6$ remains the minimal counterexample for all $k \ge 2$, and all $u<6$ remain non-counterexamples.
Induction hypothesis: For some $k \ge 2$,
$$ \lfloor v_k(u)/16 \rfloor = \begin{cases} 0,& 0 \le u \le 5,\ \ge 1,& u = 6. \end{cases} $$
Induction step: For $k+1$,
$$ v_{k+1}(u) = v_k(u) + \left\lfloor \frac{v_k(u)}{2^{k+3}} \right\rfloor. $$
- For $u<6$, $v_k(u) \le 15$. Then $v_k(u)/2^{k+3} \le 15/16 < 1$, so $\lfloor v_k(u)/2^{k+3} \rfloor = 0$. Hence $v_{k+1}(u) = v_k(u)$ and $\lfloor v_{k+1}(u)/16 \rfloor = 0 = \lfloor u/10 \rfloor$.
- For $u=6$, $v_k(6) \ge 16$, so (v_{k+1}(6) = v_k(6) + \lfloor v_k(6)/