# Powers of Two

## In lexicographic ordering

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.

© 2019 Joe Davis.