Converting Decimal to Other Bases Reverse Remainder Collection

The question is why is it that when we convert base 10 to other bases -- base 2, in particular -- we repeatedly divide the number by the new base while keeping track of the remainders and then collect the remainders in the REVERSE order.

It appears at first site that the remainders should be collected as they appear. That is,

17 / 2 = 8, r = 1

8 / 2 = 4, r = 0

4 / 2 = 2, r = 0

2 / 2 = 1, r = 0

The result is 1001. While it is correct, it seems a bit counterintuitive that the first remainder which is the result of dividing the largest number by the new base produces the least significant digit in the answer.

• You should have constructed an example where the number is not symmetric in base $2$ in the example, since you emphasized the "REVERSE." Something like $23$. Jul 19, 2017 at 18:38
• Why on earth does that seem counter intuitive? You are dividing the smallest power of the base first so you will get the finest smallest least significant remainder first. Seems utterly logical and intuitive to me. The remainder of dividing by $b^1$ will be a remainder between $0$ and $b$ where's dividing by $b^2$ will be a remainder of degree 2 between 0 and $b^2$. Jul 19, 2017 at 18:38
• @fleablood That is a good way of looking at it :) Jul 19, 2017 at 18:41
• Another thing to note is that there is purely human notation to write $7\cdot 1 +1\cdot 10+5\cdot 10^2$ as $517$. We could just as well have chosen to right them in the reverse order as our notation (and mathematically, it is easier to work with them in the order 7,1,5, in some circumstances.) Jul 19, 2017 at 18:41
• Just imagine if you were asked to convert $137$ in base $10$ to base $10$. Divide $137$ by $10$ and you get $13$ with a remainder of $7$. Jul 19, 2017 at 18:42

Set $q_0$ be your number ($17$), and $r_0=q_0\bmod 2$. We recursively compute $q_i$, $r_i$ with the Euclidean division : $$q_i=q_{i+1}\cdot 2+r_i, \quad r_i=0\;\text{ or }\;1,$$ and stop when a quotient is equal to $1$.
In the present case ($4$ steps), we obtain successively: \begin{align} 17&=q_1\cdot 2+ r_0=(q_2\cdot 2+ r_1)2+r_0\\ &=q_2\cdot 2^2+r_1\cdot 2+r_0=(q_3\cdot 2+ r_2)2^2+r_1\cdot 2+r_0 \\ &=q_3\cdot 2^3 +r_2\cdot 2^2+r_1\cdot 2+r_0=(q_4\cdot 2+r_4) 2^3 +r_2\cdot 2^2+r_1\cdot 2+r_0 \\ &=q_4\cdot2^4+r_3\cdot2^3 +r_2\cdot 2^2+r_1\cdot 2+r_0 . \end{align}
Hence $17$ (base $10$) is $\;[q_4r_3r_2r_1r_0]_2=[10001]_2$.