Project Euler 237 - Tours on a 4 X N Playing Board

Official link: https://projecteuler.net/problem=237

Thought Process

I brute forced the first few values

1. T(1) = 1

2. T(2) = 1

3. T(3) = 4

4. T(4) = 8

5. T(5) = 23

This lead me to https://oeis.org/A181688 which gives us the recursive formula T(n) = 2T(n - 1) + 2T(n - 2) - 2T(n - 3) + T(n - 4), n >= 4

Then, I use my matrix exponentiation function to get the answer very quickly!

The way this is done is as follows:

Interactive Code

Input an integer (yourinput)

Code will output T(yourinput) (mod 10^8)