Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Here's a generalization for any arithmetic sequence. With first term a0, difference d, and digit "padding" of n, the fraction that will result is:

(a0 + (d - a0)(1/10^n)) / (1 - 1/10^n)^2

For instance the sequence 1, 4, 7, 10, 13...

(1 + (3 - 1)(1/10^2)) / (1 - 1/10^2) = 1.02 / 0.9801 = 3400/3267 = 1.004 007 010 013 016...

For any kind of recursive sequence, you can find its generating function G(x) and then substitute some integer power of 0.1 for x to generate cool decimal expansions like this.

The generating function for the Fibonacci sequence is:

G(x) = x / (1 - x - x^2)

Substituting in 0.001 gives 0.001 / 0.998999 = 0.001 001 002 003 005 008...



Neat! Not familiar though with generating functions - can you pls explain how the generating function for the Fibonnaci sequence is x/(1 - x - x^2 ) ?


For Fibonacci sequence,

             x = 1x^1
      x * g(x) =        1x^2 + 1x^3 + 2x^4 + 3x^5 + 5x^6 + ...
  + x^2 * g(x) =               1x^3 + 1x^4 + 2x^5 + 3x^6 + ...
  ------------------------------------------------------------
  =       g(x) = 1x^1 + 1x^2 + 2x^3 + 3x^4 + 5x^5 + 8x^6 + ...
Hence,

     x = (1 - x - x^2) * g(x)
  g(x) = x / (1 - x - x^2)


Generating functions are amazing. One of the coolest topics in my entire undergrad math degree. This PDF is well written and will explain everything: http://courses.csail.mit.edu/6.042/fall05/ln11.pdf




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

Search: