Powers of Two in Lexicographic Order | Hacker News Reader

Powers of Two in Lexicographic Order

solipsys.co.uk

26 pointsColinWright12 comments

Cute.

For any numbers m and n, if m^x/n^y is close to but not the same as 1, this same procedure in base m will make the normalized and resorted values of 1, n, n^2, ... n^y be close to 1, m^(1/y), m^(2/y), ... m^((y-1)/y).

That is because n is approximately m^(y/x). n^2 is approximately m^(2y/x) and so on. Every time the fraction goes past 1, we rollover, and the result is that this table gets filled in with good approximations for, in this case, entries 0, 3, 6, 9, 2, 5, 8, 1, 4, 7 and then we'd roll over to 10 and be close to the starting entry for 0 (namely 1.0). And if you order by the percentage error in the approximations, you'll find that they get steadily worse as you go down that sequence.

In the case of 10 and 2 it is particularly good because 2^10 is very close to 10^3. However 3^2 = 9 is close to 10^2, 3^19 = 1162261467 is close to 10^9, 5^10 = 9765625 is close to 10^7, and 7^13 = 96889010407 is close to 10^11. All of these will produce similar tables.

The approximation will be most startling for 5^10 and 2^10, followed by 7^13. And it all has to do with how close m^x/n^y is to 1.0.

All of this is true, and helps to see what's happening as we analyse the numbers and try to create new examples, but I'm trying to find a way to explain this to non-math people. With the replies I'm getting I think I'm getting close to a couple of explanations that I can use, but it's surprisingly tricky.

What's more tricky, I find, is communicating to people what I'm trying to achieve. I found the same problem with the "photocopy a mirror" problem, and the "Four Points, Two Distances" problem. It's not a question of doing the sums, it's a problem of making the structure of the solution accessible.

But in this case I think I'm getting there.

Is it not simply a question of saying that 2^10 = 1024 is close to 10^3 - 1000. Take 10th roots of both sides and 10^(3/10) = 1.995262... is close to 2.

And therefore we have 1 = 10^0, 2 ≈ 10^0.3, 4 ≈ 10^0.6, 8 ≈ 10^0.9, 16 ≈ 10^1.2, 32 ≈ 10^1.5, 64 ≈ 10^1.8, 128 ≈ 10^2.1, 256 ≈ 10^2.4, and 512 ≈ 10^2.7.

Divide by 10s and we get 1 = 10^0, 2 ≈ 10^0.3, 4 ≈ 10^0.6, 8 ≈ 10^0.9, 1.6 ≈ 10^0.2, 3.2 ≈ 10^0.5, 6.4 ≈ 10^0.8, 1.28 ≈ 10^0.1, 2.56 ≈ 10^0.4, and 5.12 ≈ 10^0.7.

Reorder and we've got the initially surprising 1 = 10^0, 1.28 ≈ 10^0.1, 1.6 ≈ 10^0.2, 2 ≈ 10^0.3, 2.56 ≈ 10^0.4, 3.2 ≈ 10^0.5, 4 ≈ 10^0.6, 5.12 ≈ 10^0.7, 6.4 ≈ 10^0.8 and 8 ≈ 10^0.9.

Then work the 5^10 and 7^13 examples to show that it happens whenever a^b is close to a power of 10.

Leave out the other base observation.

> 1.0, 1.28, 1.6, 2.0, 2.56, 3.2, 4.0, 5.12, 6.4, 8.0

These numbers are also instantly recognizable as being closely related to the the ISO-standard 1/3 octave bands on a 31 band graphic equalizer:

30 Hz, 40, 50, 63, 80, 100, 125, 160, 200, 215, 315, 400, 500, 630 ...

There is a relation to powers of two because every three steps, the frequency doubles. These numbers are derived differently; basically according to:

                       E.g.:
  2^(1/3) ~= 1.2599    125 Hz   12.5 kHz
  2^(2/3) ~= 1.5874    160 Hz   16   kHz
  2^(3/3)  = 2         200 Hz   20   kHz

The fact that 1/10th powers of 10 approximately double in 3 steps makes those numbers close:

  10^(1/10) ~= 1.259
  10^(2/10) ~= 1.585
  10^(3/10) ~= 1.995

So why is there this three-step geometric sequence (approximately) found among that rearrangement of the powers of two?

Like from 128 to 160 (16 x 10): why is there are 2^(1/3) step?

     160      2^4 x 10            10
     ---  =   ---------    =      --    = 1.25
     128         2^7              2^3

It's simply that 1.25 is close to 10^0.1 is close to 2^(1/3). Three compounded 25% increases are close to doubling.

Note that 2^(1/3) is the same number as 8^(1/9). That's getting close to 10^(1/10).

Which exact power of ten is equal to 2^(1/3).

      10^x = 2^(1/3)

log of both sides:

         x = log10(2^1/3)
  
         x =~ 0.10034333189

Within 0.3% of 1/10th. And which power of 10 is 1.25? log10 1.25 ~= 0.09691001. Some 3% off from 0.1.

There is a relation to music here and musical intervals/scales. If we have a given root note, then 1.25X that frequency (5/4) is an ideal major third interval.

Now music geeks will know that under equal temperament, the major third interval "cuts" the octave into three equal pieces: the equal temperament major third is our 2^(1/3) = 1.2599: slightly sharp.

The closeness between 1.25 and 1.2599 is related to why equal temperament works (captures close-enough values of various musical intervals).

The power of 10 process can be represented by:

    10^(x/10)

The power of 2 thing can be represented by:

    (2^x)/(10^Ceiling[Log10[2^x] - 1)

This creates a curve which repeats every ~3: https://i.imgur.com/x72GsBf.png. lexicographic order is just effectively sampling what it'd look like stretching this curve to match the other curve because it doesn't repeat exactly as often as the sampling factor (i.e. it's not exactly every 3 rather every 3.0.1... meaning the samples become a different part of the curve). This stretching can more directly be represented by:

    (2^(x/s))/(10^Ceiling[Log10[2^(x/s)] - 1)

Visual with stretch set to 3.01: https://i.imgur.com/T1S8qwz.png. Visual of the differences: https://i.imgur.com/0H68ZU3.png

I'm not so sure there is any particularly strong relation beyond "you've created two curves and stretched them to be as close as possible". Would love to be proven wrong though but I think the ~ 3.01 number is the "magic" here and lexicographic order was just a way to "automatically" find that by resampling enough. There could be something as to why it so quickly matches, or it could just be how quickly the process works (in general?).

How does that work? ... Explanations invited.

Hold the 1 fixed. Notice in both sequences the remaining numbers are 3 interleaved ordered sets, in multiples of 2. Then watch this (just happened to post it two hours ago too)...

"Times Tables, Mandelbrot and the Heart of Mathematics" [video] https://www.youtube.com/watch?v=qhbuKbxJsk8

https://news.ycombinator.com/item?id=20558797

NB: And once again we find cycloids hiding underneath it all.

Phi is hiding in there too ...

  succ(x)  = (x^2 + 2x) / (x^2 + 1). Newton's method [0]

  ~> Decimal expansion converges quadratically 

  0.618... = [0;1,1,1,1,...]. Continued fraction grows by (+1)/
   
  0.618..., 1.0, 1.618..., 2.618.... Powers of Phi.

  φ^2  = φ + 1

  e^iτ = 0 + 1. Euler's identity (τ version) [1]

  ~> The complex exponential of the circle constant is unity.
  
  Geometrically, multiplying by e^iθ corresponds to rotating a
  complex number by an angle θ in the complex plane, which
  suggests a second interpretation of Euler’s identity:

  ~> A rotation by one turn is 1.

  √φ ≈ 4/π. Maybe a coincidence, maybe not. 

  0.283... = 2 * (π - 3.00)

[0] phi https://en.wikipedia.org/wiki/Golden_ratio#Alternative_forms

[1] tau https://tauday.com/tau-manifesto#sec-euler_s_identity

10^0.3 ≈ 1.995 is close to 2. Reordering the first ten powers of 10^0.3 and taking out whole powers of 10 gives you exactly the first ten powers of 10^0.1.

Is coincidence an acceptable answer here? I mean if you add one more power of two the whole thing is wrecked. Also if you remove one.

The second list is, by construction, a list of numbers from 1 to 8.

The first list also ranges from 1 to 8.

It isn’t shocking that when you sort the first list it aligns with the second within some margin of error.

> What's more tricky, I find, is communicating to people what I'm trying to achieve.

A different recipe:

  1. Generate powers of 2

  2. Divide by the highest power of 10 that yields a number between 1 and 10

  3. Sort these numbers

Benford's Law and an unsurprising amount of coincidence

Reply on news.ycombinator.com