We define $f(n) = a^n + b^n + c^n $ for some positive integers $(a,b,c)$ such that $a<b<c$.
Let $M$ be an integer constant, and $p \leq q$ two integers. Given the values of $f(2),f(3)$ and $f(4)$, find $$\displaystyle{\sum_{k = p}^q f(k)} \, \, \text{mod} \, M$$ If there are multiple possibilities for $(a,b,c)$ we choose the lexicographically smallest one.
Note : Since this is algorithmic, it must be done as fast as possible and we assume there is a solution.
What I've tried so far (A brute-force approach) : going through all the possible values of $a$ since we can deduce an upper bound for its value until we find the corresponding couple $(b,c)$. Then computing $\sum a^k$, $\sum b^k$ and $\sum c^k$ as geometric sums. This is a too slow approach of course.
Any better approach ?
First, express $f(2), f(3), f(4)$ in terms of elementary symmetric functionss of $a, b, c$ (Newton's formula), and then use the values to solve for said functions $s_1, s_2, s_3.$ Once you do, you see that $a, b, c$ are roots of the equation
$x^3=s_1 x^2 - s_2 x + s_3,$ and so
$f(k) = s_1 f(k-1)- s_2 f(k-2) + s_1 f(k-3),$ at which point you are done.