[math-fun] Lucas, Fibo, Phi, capital O

Lucas(n=0, 1, 2...) = 2, 1, 3, 4, 7, 11, 18... = phi^n + (-phi)^(-n) Fibonacci(n=0, 1, 2...) = 0, 1, 1, 2, 3, 5, 8... = (phi^n - (-phi)^(-n)) / sqrt(5) (True for n < 0 also.) My first thought seeing this was that Lucas(n) / Fibo(n) --> sqrt(5) and the int sequences can be done by repeated squaring, so you could get O(2^n) digits of sqrt(5) with O(n) int multiplications and only one division!! But then I thought, continued fractions probably solve the general sqrt(int) problem just as fast. And the work that Newton's method does is also about the same because the divisions only need 1, 2, 4... 2^(n-1), 2^n digits of precision. This is math. This is my brain on math. --Steve