5 ms·
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 expressi
by svat 11y ago
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.)
- bglazer 11y agoThis is a great response. Thanks for taking the time to write this.
- deleted 11y ago[deleted]
- ghosthamlet 11y agoare you a master of math?
- username3 11y agoIs any of this useful for compression?
- blahblah3 11y agoI 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 https://en.wikipedia.org/wiki/Formal_power_series