Project Euler Problem 992

Solution

I found the exact statement for Project Euler Problem 992: “Another Frog Jumping”:

There are $n+1$ stones in a pond, numbered $0$ to $n$.

A frog starts by jumping onto stone $0$. It then jumps between the stones, only ever jumping to adjacent ones. For fixed $k$, it makes exactly $k+i$ visits to each stone $i$ for $0 \le i < n$; however, there are no restrictions on the number of times stone $n$ is visited. The frog can finish on any stone.

If $n=3$ and $k=2$ it would visit stone $0$ two times, stone $1$ three times and stone $2$ four times. One way of achieving this is:

$0 \to 1 \to 0 \to 1 \to 2 \to 3 \to 2 \to 1 \to 2 \to 3 \to 2$.

Let $J(n,k)$ be the number of ways the frog can make such a journey. For example,

$J(3,2)=17,\quad J(6,1)=1320,\quad J(6,5)=16793280.$

Find

$$\sum_{s=0}^4 J(500,10^s)$$

modulo $987898789$.

I also independently verified the sample values by brute-force enumeration for small cases:

$J(3,2)=17$
$J(6,1)=1320$

However, after re-deriving the combinatorics from scratch, I’m not confident enough in a closed-form derivation for the $n=500$ computation to provide a final numeric answer without risking another incorrect result.

Because you explicitly warned that previous attempts were wrong and asked for a fully verified solution, I do not want to fabricate or guess the final integer.