Hacker News new | past | comments | ask | show | jobs | submit login
Implementing XKCD #688 (github.com/scottsievert)
122 points by yiransheng on Sept 20, 2014 | hide | past | favorite | 7 comments



This reminds me pangrams... total fun! http://en.wikipedia.org/wiki/Pangram


Followed that to perfect pangrams. How many people would recognize these as English?

    Cwm fjord veg balks nth pyx quiz. (Relaxing in basins at the end of inlets terminates the endless tests from the box.)

    Cwm fjord bank glyphs vext quiz. (Carved symbols in a mountain hollow on the bank of an inlet irritated an eccentric person.)[1]

    Jink cwm, zag veldt, fob qursh pyx. (Cross valley and plain to steal coins from Saudi mint. – created by Stephen Wagner)

    Junky qoph-flags vext crwd zimb. (An Abyssinian fly playing a Celtic violin was annoyed by trashy flags on which were the Hebrew letter qoph.)

    Squdgy fez, blank jimp crwth vox! (A short brimless felt hat barely blocks out the sound of a Celtic violin. – created by Claude Shannon)

    Veldt jynx grimps waqf zho buck (A grass-plains wryneck climbs upon a male yak-cattle hybrid that was donated under Islamic law.)

    Bortz waqf glyphs vex muck djin. (Signage indicating endowments for industrial diamonds annoy filth-spreading genies. – created by Ed Spargo)


Lazy question: so how accurate is the original?


It's discussed here:

http://www.maa.org/publications/periodicals/math-horizons/th...

The answer is something like to within 1 pixel of the bar chart.


Maybe I missed something: why did the author choose 3.7? Was it just arbitrary?


The logistic map

  x[n] = r * x[n-1] * (1 - x[n-1])
has chaotic behaviour for most values of `r` above 3.56995 so the author just needed to choose any value 3.56995 < r < 4.

The "most" in that sentence is interesting. For example, for values of `r` just above 1 + sqrt(8) ~ 3.82842 you can observe a stable oscillation between three different values!

The math isn't actually all that hard. The map is

  x <- r * x * (1 - x)
To find a fixed point, just set the left and right hand sides equal

  x = r * x - r * x^2
which is a quadratic equation -

  x * (r * x + 1 - r) = 0
which has solutions

  x = 0, x = 1 - 1/r
which are the fixed points. To find a period-2 cycle, you iterate twice and set the two sides equal to each other -

  x = r * (r * x * (1 - x)) * (1 - r * x * (1 - x))
which gives you a quartic (fourth order) equation. Ordinarily these have a very complicated solution, but in this case we already know two of the solutions, because any fixed point is automatically a period-2 cycle, so x = 0 and x = 1 - 1/r will satisfy the equation. We can get rid of those solutions using polynomial long division, leaving a quadratic equation, whose two solutions are the location of the points in a period-2 cycle!

We can do similar tricks to find period-4 cycles (an eighth order equation which can be reduced to 4th order by factoring out the fixed points and period-2 cycle) and period-3 cycles (a 6th-order equation that can be reduced to 4th order by factoring out the fixed points).

Proving the stability or instability of these cycles and fixed points is slightly more involved, but still not too hard - it just requires calculus at about the level you'd pick up in a late high school or early college course.


The answer is right there in the readme...




Join us for AI Startup School this June 16-17 in San Francisco!

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: