lxiv. Monkey and Coconuts

Problem. $n$ sailors gather a pile of coconuts. During the night each sailor in turn divides the pile into $n$ equal parts with one left over (given to the monkey), hides one part, and puts the rest back. In the morning the remaining pile again divides into $n$ parts with one left over. Smallest initial pile?

Answer: $n^{n+1}-n+1$; for 5 sailors, $15621$.

long long coconuts(long long n) {                  // smallest pile: n sailors, each night one to the monkey then 1/n taken; morning split also leaves 1
    long long p = 1; for (int i = 0; i <= n; i++) p *= n;
    return p - n + 1;
}

Proof: the smallest pile

Add $n-1$ “phantom” coconuts: if the pile $x$ satisfies $x\equiv 1(\mathrm{mod}n)$, then $x+(n-1)$ is divisible by $n$, and after one night step the new pile $\frac{n-1}{n}(x-1)$ plus $n-1$ equals $\frac{n-1}{n}(x+n-1)$. So with $y=x+n-1$, each of the $n+1$ divisions (n nights plus the morning) multiplies $y$ by $\frac{n-1}{n}$ and needs it to be a multiple of $n$ beforehand. Hence $y$ must be divisible by $n^{n+1}$, and the smallest is $y=n^{n+1}$, giving $x=n^{n+1}-n+1$. Checked by brute-force simulation for $n\le 6$.