tribonacci.egi

-- Tribonacci sequence using matrix exponentiation

def m : Integer := 3

def A : Matrix Integer :=
  generateTensor
    (\match as list integer with
      | [#1, _] -> 1
      | [$x, #(x - 1)] -> 1
      | _ -> 0)
    [m, m]

assertEqual "transition matrix A"
  A
  [| [| 1, 1, 1 |], [| 1, 0, 0 |], [| 0, 1, 0 |] |]

def B : Vector Integer :=
  generateTensor
    (\[x] -> if x = 1 then 1 else 0)
    [m]

assertEqual "initial vector B"
  B
  [| 1, 0, 0 |]

assertEqual "A * B"
  (M.* A B)
  [| 1, 1, 0 |]

assertEqual "A^2 * B"
  (M.* (M.power A 2) B)
  [| 2, 1, 1 |]

assertEqual "A^3 * B"
  (M.* (M.power A 3) B)
  [| 4, 2, 1 |]

assertEqual "A^4 * B"
  (M.* (M.power A 4) B)
  [| 7, 4, 2 |]

assertEqual "A^5 * B"
  (M.* (M.power A 5) B)
  [| 13, 7, 4 |]

assertEqual "A^100 * B (100th tribonacci)"
  (M.* (M.power A 100) B)
  [| 180396380815100901214157639, 98079530178586034536500564, 53324762928098149064722658 |]