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.