トリボナッチ数列

-- 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 |]

リンク

Egison 数学ノート目次に戻る