Exponential model (Advent of code 2021 day 6)

(Expanding on Joppy's comment).

For each $t\in \mathbb N$ and $i\in \{0,\dots,8\}$, let $v_{t,i}$ be the number of fish with level $i$ at time $t$, and let $v_t=(v_{0,t},v_{1,t},\dots,v_{8,t})$. You can show that $v_{t+1}$ is determined from $v_t$ via matrix multiplication. Specifically, $$ v_{t+1}=Av_t,\qquad A=\begin{bmatrix} 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \end{bmatrix} $$ It follows by induction that that $$ v_t = A^t v_0, $$ giving a simple formula for the fish distribution at time $t$. If you like, this implies the number of fish at time $t$ is given by the formula ${\bf 1}^{\top}Av_t$, where ${\bf 1}$ is the column vector with nine ones.

If you further like, you could put this matrix in Jordon form, which should give a formula for the number of fish at time $t$ in the form $\sum_i p_i(t) (\lambda_i)^t$, where $\{\lambda_i\}_{i\in I}$ is the set of eigenvalues of $A$, and $p_i(t)$ are certain polynomials in $t$. However, in this case the eigenvalues are irrational, so this form is not well suited for exact integer computation. The previous formula is excellent for computation, since you can compute $A^t$ with only $O(\log t)$ matrix multiplications using exponentiation by squaring.