I thought I would take the chance to provide the general solution to all of these puzzles.

If anyone has any questions I can motivate the solution here.


#! /usr/bin/env nix-shell
#! nix-shell -p "haskell.packages.ghc822.ghcWithPackages (pkgs: [pkgs.matrix])" -i "cabal exec -- runghc"

module Main where

import Control.Applicative ((<$>))
import qualified Data.Matrix as Matrix
import Data.Matrix ((<->))

dot :: Num a => Matrix.Matrix a -> Matrix.Matrix a -> Matrix.Matrix a
dot = Matrix.multStd

matrixExp :: Integral a => Matrix.Matrix a -> Integer -> a -> Matrix.Matrix a
matrixExp m n modulus
| n <= 0 = Matrix.identity (Matrix.nrows m)
| odd n = (`mod` modulus) <$> m `dot` (matrixExp m (n-1) modulus)
| otherwise = (`mod` modulus) <$> mHalfN `dot` mHalfN
where mHalfN = matrixExp m (n `div` 2) modulus

series :: [Integer] -> Integer -> Integer -> Integer
series coeffs n modulus = Matrix.getElem 1 1 $ (matrixExp u n modulus)
where
m = length coeffs
u = Matrix.fromLists [coeffs]
<->
(Matrix.extendTo 0 (m - 1) l $ Matrix.identity (m - 1))

fib :: Integer -> Integer -> Integer
fib = series [1,1]

pell :: Integer -> Integer -> Integer
pell = series [2,1]

trib :: Integer -> Integer -> Integer
trib = series [1,1,1]

extreme :: Integer -> Integer -> Integer
extreme = series [1,1,0,0,5,0,0,0,3]

main :: IO ()
main = do
putStrLn $ "MD 1: " ++ show (fib 10 (10^10))
putStrLn $ "MD 2: " ++ show (fib (10^7) (10^10))
putStrLn $ "MD 2 (*): " ++ show (fib (10^100) (10^10))
putStrLn $ "MD 3: " ++ show (pell (10^7) (10^10))
putStrLn $ "MD 3 (*): " ++ show (pell (10^100) (10^10))
putStrLn $ "MD 4: " ++ show (trib (10^7) (10^10))
putStrLn $ "MD 4 (*): " ++ show (trib (10^100) (10^10))
putStrLn $ "MD 5: " ++ show (extreme (10^7) (10^10))
putStrLn $ "MD 5 (*): " ++ show (extreme (10^100) (10^10))


This outputs:


MD 1: 89
MD 2: 7120937501
MD 2 (*): 2460937501
MD 3: 4570126209
MD 3 (*): 9020126209
MD 4: 7912206465
MD 4 (*): 6198029313
MD 5: 6777244134
MD 5 (*): 4404226404