## Powers of 2 in lexicographic ordering

This is an old post, migrated from my old blog to test out Write.as's MathJax support.

A recent link on lobste.rs caught my attention: Take the first 10 powers of 2 (starting from zero), sorted in lexicographic order, $$1, 128, 16, 2, 256, 32, 4, 512, 64, 8$$ Now, put a decimal point after the first digit in each, $$1.0, 1.28, 1.6, 2.0, 2.56, 3.2, 4.0, 5.12, 6.4, 8.0$$ At first glance, it's hard to see any patterns in this, but if we take $10^{n/10}$, for $n = 0,\ldots,9$, we get the suspiciously similar sequence $$1.0, 1.259, 1.585, 1.995, 2.512, 3.162, 3.981, 5.012, 6.310, 7.943$$ One might ask why this happens intuitively. I believe that the most intuitive explanation stems from the simple fact that $\log_{10} 2 \approx 0.3$.

How does this come into play? Well let's look at the sequence of shifted
powers of two. Shifting a number so that the decimal point sits after the first non-zero digit is the same as dividing by the highest power of 10 less than that number. For a given $n$, that power of 10 is given by $$10^{\lfloor \log_{10} n \rfloor} $$ So, terms in our sequence can all be written in the form, $$
\begin{aligned}
\frac{2^n}{10^{\lfloor \log_{10} 2^n \rfloor}} &=
\frac{10^{n \log_{10} 2}}{10^{\lfloor n \log_{10} 2 \rfloor}} \\
&= 10^{n \log_{10} 2 – \lfloor n \log_{10} 2 \rfloor} \\
&= 10^{\{ n \log_{10} 2 \}}
\end{aligned} $$ where $\{x\}$ denotes the fractional part of $x$, i.e. $\{ x \} = x -\lfloor x \rfloor$. Evaluating this for $n = 0, \ldots, 9$, gives in sequence, $$1.0, 2.0, 4.0, 8.0, 1.6, 3.2, 6.4, 1.28, 2.56, 5.12$$ Okay, they're shifted, but not lexicographically sorted. In fact, the lexicographic ordering is a red herring, we can achieve the same sequence by *first shifting the decimal place and then sorting in ascending order*!

So where does the correspondence between this and $10^{n/10}$ appear? Well, because $\log_{10} 2 \approx 0.3$, we have that our terms in our sequence can be approximated as $$\begin{aligned} 1 &\approx 10^{{ 0.3 \cdot 0 }} = 10^0 = 1 \\ 2 &\approx 10^{{ 0.3 \cdot 1 }} = 10^{0.3} = 1.995 \\ 4 &\approx 10^{{ 0.3 \cdot 2 }} = 10^{0.6} = 3.981 \\ 8 &\approx 10^{{ 0.3 \cdot 3 }} = 10^{0.9} = 7.943 \\ 1.6 &\approx 10^{{ 0.3 \cdot 4 }} = 10^{0.2} = 1.585 \\ 3.2 &\approx 10^{{ 0.3 \cdot 5 }} = 10^{0.5} = 3.162 \\ 6.4 &\approx 10^{{ 0.3 \cdot 6 }} = 10^{0.8} = 6.310 \\ 1.28 &\approx 10^{{ 0.3 \cdot 7 }} = 10^{0.1} = 1.259 \\ 2.56 &\approx 10^{{ 0.3 \cdot 8 }} = 10^{0.4} = 2.512 \\ 5.12 &\approx 10^{{ 0.3 \cdot 9 }} = 10^{0.7} = 5.012 \\ \end{aligned} $$ Similarly, $$1024 = 2^{10} = 10^{10 \log_{10} 2} \approx 10^{0.3 \cdot 10} = 10^3 = 1000$$A relation that should be second nature to anybody with an interest in computers.