Hacker News new | comments | show | ask | jobs | submit login

Short answer: the denominator is (10^48 - 10^24 - 1).

Long answer follows.

It's actually easier to understand if you work backwards and arrive at the expression yourself, by asking yourself: "If I wanted the number that starts like 0.0...000 0...001 0...001 0...002 0...003 0...005 0...008 ... (with each block being 24 digits long), how would I express that number?"

Well, calling the Fibonacci numbers f_n (with f_1=0), that decimal expansion you want is sum (f_n 10^(-24n)) over n≥1. This is sum (f_n x^n) evaluated at x = 10^(-24). It is easy to work out (especially if you know the trick already) that sum (f_n x^n) = x^2 / (1 - x - x^2), which at x = 10^(-24) gives that the number we want is 1/(10^48 - 10^24 - 1), which is exactly what 1/999999999999999999999998999999999999999999999999 is.

This may be more interesting if you consider more examples:

* if we want the number 0 . 0001 0002 0004 0008 0016 0032 0064 0128..., then it is sum (2^(n-1) 10000^(-n)). We can calculate that sum(2^(n-1) x^n) is x/(1-2x), which at x = 1/10000 becomes 1/9998. And indeed 1/9998 = 0.0001000200040008001600320064012802560512102420484096...

Similarly,

* if we want the number 0 . 000 001 002 003 004 005 ..., then it is sum ((n-1) 1000^(-n)). And sum ((n-1) x^n) is x^2/(1-x)^2, and putting x = 1/1000 in it gives 1/999^2 = 1/998001, and indeed 1/998001 = 0.000001002003004005006007008009010011012013014015016...

Basically whenever sum (a_n x^n) has a nice form (aka the generating function of the sequence), you can plug in x = 1/(some power of 10) and get such pretty decimal expansions.

(Edit: Formatting, and the "short answer" at the top.)




I recommend generatingfunctionology by herbert wilf for the interested.

The beautiful idea here is to consider formal power series (encoding sequences of values in polynomials without demanding convergence) https://en.wikipedia.org/wiki/Formal_power_series


Is any of this useful for compression?


This is a great response. Thanks for taking the time to write this.


are you a master of math?




Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | DMCA | Apply to YC | Contact

Search: