Calculating (3 + sqrt(5))^n exactly
Octave, 26 bytes
[3 5;1 3]**input('')*[1;0]
Because (a+b*sqrt(5)) * (3+sqrt(5)) = (3a+5b) + (a+3b) * sqrt(5),
multiplying input vector
| 1 | /* a = 1 */
| 0 | /* b = 0 */
which stands for 1 = (3+sqrt(5))^0 by matrix
| 3 5 |
| 1 3 |
seems natural. Instead of looping n
times, we rather raise the matrix to the power of n
and then multiply it by input vector.
Python 2, 50
a=1;b=0
exec"a,b=3*a+5*b,3*b+a;"*input()
print a,b
Multiplies by 3+sqrt(5)
repeatedly by its action on the pair (a,b)
representing a+b*sqrt(5)
. Equivalent to starting with the column vector [1,0]
and left-multiplying n
times by the matrix [[3,5],[1,3]]
.
Julia, 22 20 bytes
n->[3 5;1 3]^n*[1;0]
This creates a lambda function which takes a single integer as input and returns a 2-element vector of integers corresponding to the solution [a, b]. To call it, give it a name, e.g. f=n->...
.
Start by multiplying
We can then translate the right hand side of this equation into a 2-column matrix, where the first corresponds to the coefficient of a and the second to the coefficient of b:
Multiply this matrix by itself n times, then right multiply by the column vector (1, 0), and POOF! Out pops the solution vector.
Examples:
julia> println(f(0))
[1,0]
julia> println(f(5))
[1968,880]