Calculating (3 + sqrt(5))^n exactly Today your goal is to find integers a and b given non-negative integer n such that:



You should write a program or a function that takes parameter n and outputs a and b in a format of your choice.

Standard loopholes apply. Additionally, it's intended that you implement the above problem using basic arithmetic yourself. So you may not use built-in exact algebra functionality, rationals, or functions implementing non-trivial mathematical constructs (for example the Lucas sequence).

Shortest code in bytes wins.



Example input/output:


  0 &rightarrow; 1, 0
  1 &rightarrow; 3, 1
  2 &rightarrow; 14, 6
  3 &rightarrow; 72, 32
  4 &rightarrow; 376, 168
  5 &rightarrow; 1968, 880
  6 &rightarrow; 10304, 4608
  7 &rightarrow; 53952, 24128
  8 &rightarrow; 282496, 126336
  9 &rightarrow; 1479168, 661504
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.