3 ms·
And in base b, it's 1/( b (b-1) -1 ).
by spicyj 17y ago
And in base b, it's 1/( b (b-1) -1 ).
- eru 17y agoYes. I was too lazy to type that. :o) Anyway, it also works with polynomials (and even better there): x / (1-x-x^2) = 0 + x + x^2 + 2 x^2 + 3 x^3 + 5 x^4 + ... (FYI: Look up "Generating Functions" in "Concrete Math" or on the Web. A lot of operations on sequences e.g. adding them, multiplying by a scalar, convoluting them, splicing, taking every n-th element, can be done efficiently and elegantly on their generating function.) http://en.wikipedia.org/wiki/Fibonacci_number#Power_series http://en.wikipedia.org/wiki/Fibonacci_number#Power_series