Generating Hexanacci numbers using fast exponentiation

Instead of writing a closed-form formula you can compute it using matrix multiplication, or specifically matrix fast pow.

Specifically, let's assume the sequence is x(i).

Then we can construct a matrix A such that:

[x(i+1), x(i+2), x(i+3), x(i+4), x(i+5), x(i+6)]^T = A * [x(i), x(i+1), x(i+2), x(i+3), x(i+4), x(i+5)]^T

This matrix will look like:

0 1 0 0 0 0
0 0 1 0 0 0
0 0 0 1 0 0
0 0 0 0 1 0
0 0 0 0 0 1
1 1 1 1 1 1

Now if you compute Aⁿ that allows you to make n steps at time:

[x(i+n), x(i+n+1), x(i+n+2), x(i+n+3), x(i+n+4), x(i+n+5)]^T = Aⁿ * [x(i), x(i+1), x(i+2), x(i+3), x(i+4), x(i+5)]^T

Aⁿ can be computed in O(log(n)) matrix multiplications.