Sailors, monkey and coconuts

According to MathWorld, the smallest positive solution is $15621$ coconuts. The smallest positive solution if the coconuts divide evenly at the end, with none left over for the monkey, is $3121$. The link gives an outline of the solution to this classic Diophantine problem. A detailed solution can be found in this PDF, alone with the slick shortcut solution:

By inspection $-4$ is a solution: when it’s divided into $5$ piles of $-1$ with $1$ left over for the monkey, and one of the piles is removed, $-4$ coconuts remain for the next division. It’s also not too hard to see that $5^6=15625$ can be added to any solution to obtain another, since the pile is divided into $5$ piles $6$ times; thus, $15621$ is a solution.


Let $x_k$ be the number of coconuts left after the $k$-th sailor has divided them into $5$ piles, hidden his pile, and given the remaining coconut to the monkey. Hence,

$$x_{k+1} = \frac 45 (x_k - 1) = \frac 45 x_k - \frac 45$$

and, thus,

$$x_k = \left(\frac 45\right)^k x_0 - \sum_{\ell=1}^k \left(\frac 45\right)^{\ell} = \cdots = (x_0 + 4) \left(\frac 45\right)^k - 4$$

After the $5$ sailors' interventions, one coconut is given to the monkey and the remaining ones are divided evenly in $5$ piles. Thus, $x_5 - 1$ is not merely a nonnegative integer, but also a multiple of $5$, i.e., there exists $m \in \mathbb N$ such that $x_5 - 1 = 5 m$. Thus, the initial number of coconuts is given by

$$x_0 = - 4 + \frac{5^6}{4^5} (m+1)$$

The first natural $m$ that makes $x_0$ integral is $m = 4^5 - 1$. The first admissible $x_0$ is thus $$x_0 = 5^6 - 4 = \color{blue}{15621}$$

Computing $x_0, x_1, \dots, x_5$ in Haskell,

λ> take 6 $ iterate (\x->(div (4*(x-1)) 5)) 15621
[15621,12496,9996,7996,6396,5116]

Note that $x_5 = 5116 = 1 + 5 \cdot 1023$.