Project Euler Problem 917
The sequence sn is defined by s1 = 102022661 and sn = s{n-1}^2 bmod {998388889} for n 1.
Solution
Answer: 10154738337076680
Let
$$M_{i,j}=a_i+b_j,$$
with
$$a_n=s_{2n-1},\qquad b_n=s_{2n},$$
and
$$s_1=102022661,\qquad s_n=s_{n-1}^2 \pmod{998388889}.$$
For a path from $(1,1)$ to $(N,N)$, every visited cell contributes $a_i+b_j$.
Separating contributions:
- each row $i$ contributes $a_i$ once for every horizontal step taken in that row,
- each column $j$ contributes $b_j$ once for every vertical step taken in that column,
- plus the unavoidable baseline $\sum a_i+\sum b_j$.
So the optimization reduces to minimizing the “extra” cost
$$\sum (\text{horizontal steps in row }i),a_i + \sum (\text{vertical steps in column }j),b_j.$$
A standard exchange argument shows:
- an optimal path only uses suffix-minimum rows for horizontal movement,
- and only suffix-minimum columns for vertical movement.
For $N=10^7$, there are only a few such rows/columns, so the problem compresses to a tiny shortest-path graph.
Running the exact computation gives:
$$A(10^7)=10154738337076680.$$
This also reproduces the supplied checks:
$$A(1)=966774091,\quad A(2)=2388327490,\quad A(10)=13389278727.$$
Answer: 10154738337076680