finding a constant runtime algorithm to calculate a recursive summation Suppose we have a sequence of integers $A_n$ where $A_0$, ..., $A_{k=1}$ < $50$, and for each subsequent term in the sequence, $A_i = A_{i-1}b_1 + A_{i-2}b_2 +... + A_{i-k}b_k$. ($A_0$ through $A_{k-1}$ and all $b_i$ (where i is 1 through k) are givens. I am to devise an algorithm that computes $A_n \mod 50$ and would run in a constant time (treat k as a constant), but I'm having a bit of a trouble solving this.
I get that since each $A_i$ is given by k numbers preceding it, and every $A_j$ (regardless of whether they were original 'given' numbers or subsequent terms) has 50 different possible values, there must be $50^k$ different possible ways to get $A_i$, but since all $A_j$ are modded by $50$, $A_i$ should in fact only have 50 different possible values. So I don't quite understand this discrepancy, and I'm further unsure of how to use this fact (if at all) to find the algorithm that runs in a constant time.
*Arithmetic operations on numbers of size O(log n) are done in constant time.
Any help would be greatly appreciated!
 A: There is no really constant algorithm, because we need at the very least to read $n$, which is already $O(\log n)$.
There is an algorithm that uses $O(1)$ arithmetic operations with numbers of order $O(n)$ and $O(1)$ other operations. Say $\vec B_i = \langle A_{i - k}, A_{i - k + 1}, \ldots, A_{i - 1}\rangle$. Note that we can find $A_i$ in constant time if we know $\vec B_i$.
There are only $50^k$ possible values for $\vec B_i$, and if $\vec B_i = \vec B_j$ then $\vec B_{i + x} = \vec B_{j + x}$ for any $x \geq 0$.
So for some $p, q < 50^k$ we have $\vec B_p = \vec B_{p + q}$ and thus $\vec B_i = \vec B_{i + c\cdot q}$ for any $i \geq p$, $c > 0$. We can find such $p$ and $q$ in constant time by brute force. In other words, $A_i$ is periodic with both period and pre-period part having length of at most $50^k$, and we can find these lengths in constant time.
Now, we can write $n = t + c\cdot q$ where $p \leq t < p + q$, and thus get $\vec B_n = \vec B_t$.
We can find $\vec B_t$ in constant time, and from it find $A_n$ in constant time.
The only non-constant time is to find $t$, and to do it we need to read $n$ and perform some arithmetic on it, which takes $O(\log n)$ time. If we say that arithmetic on input-size numbers is constant time, then this algorithm runs in $O(1)$.
The discrepancy you found is because $A_i = A_j$ doesn't imply $A_{i + 1} = A_{j + 1}$, so we need to know more than $1$ previous element to find next, and there are more than $50$ different values they can take.
