Using a sieve

The search space can be reduced by a series of increasingly larger factors by observing the structure of the problem so that a bit of trial and error finds the solution. The search space is much smaller if one starts with the number of coconuts received by each man in the morning division, because that number is much smaller than the number in the original pile.

If F is the number of coconuts each sailor receives in the final division in the morning, the pile in the morning is 5F, which must also be divisible by 4, since the last sailor in the night combined 4 piles for the morning division. So the morning pile, call the number n, is a multiple of 20. The pile before the last sailor woke up must have been 5/4(n)+1. If only one sailor woke up in the night, then 5/4(20)+1 = 26 works for the minimum number of coconuts in the original pile. But if two sailors woke up, 26 is not divisible by 4, so the morning pile must be some multiple of 20 that yields a pile divisible by 4 before the last sailor wakes up. It so happens that 3*20=60 works for two sailors: applying the recursion formula for n twice yields 96 as the smallest number of coconuts in the original pile. 96 is divisible by 4 once more, so for 3 sailors awakening, the pile could have been 121 coconuts. But 121 is not divisible by 4, so for 4 sailors awakening, one needs to make another leap. At this point, the analogy becomes obtuse, because in order to accommodate 4 sailors awakening, the morning pile must be some multiple of 60: if one is persistent, it may be discovered that 17*60=1020 does the trick and the minimum number in the original pile would be 2496. A last iteration on 2496 for 5 sailors awakening, i.e. 5/4(2496)+1 brings the original pile to 3121 coconuts.

Blue coconuts

Another device is to use extra objects to clarify the division process. Suppose that in the evening we add four blue coconuts to the pile. Then the first sailor to wake up will find the pile to be evenly divisible by five, instead of having one coconut left over. The sailor divides the pile into fifths such that each blue coconut is in a different fifth; then he takes the fifth with no blue coconut, gives one of his coconuts to the monkey, and puts the other four fifths (including all four blue coconuts) back together. Each sailor does the same. During the final division in the morning, the blue coconuts are left on the side, belonging to no one. Since the whole pile was evenly divided 5 times in the night, it must have contained 5⁵ coconuts: 4 blue coconuts and 3121 ordinary coconuts.

The device of using additional objects to aid in conceptualizing a division appeared as far back as 1912 in a solution due to Norman H. Anning.^[3][16]

A related device appears in the 17-animal inheritance puzzle: A man wills 17 horses to his three sons, specifying that the eldest son gets half, the next son one-third, and the youngest son, one-ninth of the animals. The sons are confounded, so they consult a wise horse trader. He says, "here, borrow my horse." The sons duly divide the horses, discovering that all the divisions come out even, with one horse left over, which they return to the trader.

Base 5 numbering

A simple solution appears when the divisions and subtractions are performed in base 5. Consider the subtraction, when the first sailor takes his share (and the monkey's). Let n₀,n₁,... represent the digits of N, the number of coconuts in the original pile, and s₀,s₁... represent the digits of the sailor's share S, both base 5. After the monkey's share, the least significant digit of N must now be 0; after the subtraction, the least significant digit of N' left by the first sailor must be 1, hence the following (the actual number of digits in N as well as S is unknown, but they are irrelevant just now):

n5n4n3n2n1 0   (N5)
  s4s3s2s1s0   (S5)
          1   (N'5)

The digit subtracted from 0 base 5 to yield 1 is 4, so s₀=4. But since S is (N-1)/5, and dividing by 5₅ is just shifting the number right one position, n₁=s₀=4. So now the subtraction looks like:

n5n4n3n2 4 0
  s4s3s2s1 4
          1

Since the next sailor is going to do the same thing on N', the least significant digit of N' becomes 0 after tossing one to the monkey, and the LSD of S' must be 4 for the same reason; the next digit of N' must also be 4. So now it looks like:

n5n4n3n2 4 0
  s4s3s2s1 4
        4 1

Borrowing 1 from n₁ (which is now 4) leaves 3, so s₁ must be 4, and therefore n₂ as well. So now it looks like:

n5n4n3 4 4 0
  s4s3s2 4 4
        4 1

But the same reasoning again applies to N' as applied to N, so the next digit of N' is 4, so s₂ and n₃ are also 4, etc. There are 5 divisions; the first four must leave an odd number base 5 in the pile for the next division, but the last division must leave an even number base 5 so the morning division will come out even (in 5s). So there are four 4s in N following a LSD of 1: N=44441₅=3121₁₀

A numerical approach

A straightforward numeric analysis goes like this: If N is the initial number, each of 5 sailors transitions the original pile thus:

N => 4(N–1)/5 or equivalently, N => 4(N+4)/5 – 4.

Repeating this transition 5 times gives the number left in the morning:

N => 4(N+4)/5 – 4

   => 16(N+4)/25 – 4

   => 64(N+4)/125 – 4

   => 256(N+4)/625 – 4

   => 1024(N+4)/3125 – 4

Since that number must be an integer and 1024 is relatively prime to 3125, N+4 must be a multiple of 3125. The smallest such multiple is 3125 · 1, so N = 3125 – 4 = 3121; the number left in the morning comes to 1020, which is evenly divisible by 5 as required.

Modulo congruence

A simple succinct solution can be obtained by directly utilizing the recursive structure of the problem: There were five divisions of the coconuts into fifths, each time with one left over (putting aside the final division in the morning). The pile remaining after each division must contain an integral number of coconuts. If there were only one such division, then it is readily apparent that 5 · 1+1=6 is a solution. In fact any multiple of five plus one is a solution, so a possible general formula is 5 · k – 4, since a multiple of 5 plus 1 is also a multiple of 5 minus 4. So 11, 16, etc also work for one division.^[17]

If two divisions are done, a multiple of 5 · 5=25 rather than 5 must be used, because 25 can be divided by 5 twice. So the number of coconuts that could be in the pile is k · 25 – 4. k=1 yielding 21 is the smallest positive number that can be successively divided by 5 twice with remainder 1. If there are 5 divisions, then multiples of 5⁵=3125 are required; the smallest such number is 3125 – 4 = 3121. After 5 divisions, there are 1020 coconuts left over, a number divisible by 5 as required by the problem. In fact, after n divisions, it can be proven that the remaining pile is divisible by n, a property made convenient use of by the creator of the problem.

A formal way of stating the above argument is:

The original pile of coconuts will be divided by 5 a total of 5 times with a remainder of 1, not considering the last division in the morning. Let N = number of coconuts in the original pile. Each division must leave the number of nuts in the same congruence class (mod 5). So,

${\displaystyle N\equiv 4/5\cdot (N-1)}$ (mod 5) (the –1 is the nut tossed to the monkey)

${\displaystyle 5N\equiv 4N-4}$ (mod 5)

${\displaystyle N\equiv -4}$ (mod 5) (–4 is the congruence class)

So if we began in modulo class –4 nuts then we will remain in modulo class –4. Since ultimately we have to divide the pile 5 times or 5^5, the original pile was 5^5 – 4 = 3121 coconuts. The remainder of 1020 coconuts conveniently divides evenly by 5 in the morning. This solution essentially reverses how the problem was (probably) constructed.

The Diophantine equation and forms of solution

The equivalent Diophantine equation for this version is:

${\displaystyle 1024N=15625F+8404}$ (1)

where N is the original number of coconuts, and F is the number received by each sailor on the final division in the morning. This is only trivially different than the equation above for the predecessor problem, and solvability is guaranteed by the same reasoning.

Reordering,

${\displaystyle 1024N-15625F=8404}$ (2)

This Diophantine equation has a solution which follows directly from the Euclidean algorithm; in fact, it has infinitely many periodic solutions positive and negative. If (x₀, y₀) is a solution of 1024x–15625y=1, then N₀=x₀ · 8404, F₀=y₀ · 8404 is a solution of (2), which means any solution must have the form

${\displaystyle {\begin{cases}N=N_{0}+15625\cdot t\\F=F_{0}+1024\cdot t\end{cases}}}$(3)

where ${\displaystyle t}$ is an arbitrary parameter that can have any integral value.

A reductionist approach

One can take both sides of (1) above modulo 1024, so

${\displaystyle 1024N=15625F+8404\mod 1024}$

Another way of thinking about it is that in order for ${\displaystyle n}$ to be an integer, the RHS of the equation must be an integral multiple of 1024; that property will be unaltered by factoring out as many multiples of 1024 as possible from the RHS. Reducing both sides by multiples of 1024,

${\displaystyle 0=(15625F-15\cdot 1024F)+(8404-8\cdot 1024)\mod 1024}$

subtracting,

${\displaystyle 0=265F+212\mod 1024}$

factoring,

${\displaystyle 0=53\cdot (5F+4)\mod 1024}$

The RHS must still be a multiple of 1024; since 53 is relatively prime to 1024, 5F+4 must be a multiple of 1024. The smallest such multiple is 1 · 1024, so 5F+4=1024 and F=204. Substituting into (1)

${\displaystyle 1024N=15625\cdot 204+8404\Rightarrow N={\frac {3195904}{1024}}\Rightarrow N=3121}$

Euclidean algorithm

The Euclidean algorithm is quite tedious but a general methodology for solving rational equations ax+by=c requiring integral answers. From (2) above, it is evident that 1024 (2¹⁰) and 15625 (5⁶) are relatively prime and therefore their GCD is 1, but we need the reduction equations for back substitution to obtain N and F in terms of these two quantities:

First, obtain successive remainders until GCD remains:

15625 = 15·1024 + 265 (a)

1024 = 3·265 + 229 (b)

265 = 1·229 + 36 (c)

229 = 6·36 + 13 (d)

36 = 2·13 + 10 (e)

13 = 1·10 + 3 (f)

10 = 3·3 + 1 (g) (remainder 1 is GCD of 15625 and 1024)

1 = 10 – 3(13–1·10) = 4·10 – 3·13 (reorder (g), substitute for 3 from (f) and combine)

1 = 4·(36 – 2·13) – 3·13 = 4·36 – 11·13 (substitute for 10 from (e) and combine)

1 = 4·36 – 11·(229 – 6·36) = –11·229 + 70*36 (substitute for 13 from (d) and combine)

1 = –11·229 + 70·(265 – 1·229) = –81·229 + 70·265 (substitute for 36 from (c) and combine)

1 = –81·(1024 – 3·265) + 70·265 = –81·1024 + 313·265 (substitute for 229 from (b) and combine)

1 = –81·1024 + 313·(15625 – 15·1024) = 313·15625 – 4776·1024 (substitute for 265 from (a) and combine)

So the pair (N₀,F₀) = (-4776·8404, -313*8404); the smallest ${\displaystyle t}$ (see (3) in the previous subsection) that will make both N and F positive is 2569, so:

${\displaystyle N=N_{0}+15625\cdot 2569=3121}$

${\displaystyle F=F_{0}+1024\cdot 2569=204}$

Continued fraction

Alternately, one may use a continued fraction, whose construction is based on the Euclidean algorithm. The continued fraction for 1024⁄15625 (0.065536 exactly) is [;15,3,1,6,2,1,3];^[18] its convergent terminated after the repetend is 313⁄4776, giving us x₀=–4776 and y₀=313. The least value of t for which both N and F are non-negative is 2569, so

${\displaystyle N=-4776\cdot 8404+15625\cdot 2569=3121}$.

This is the smallest positive number that satisfies the conditions of the problem.

A generalized solution

When the number of sailors is a parameter, let it be ${\displaystyle m}$, rather than a computational value, careful algebraic reduction of the relation between the number of coconuts in the original pile and the number allotted to each sailor in the morning yields an analogous Diophantine relation whose coefficients are expressions in ${\displaystyle m}$.

The first step is to obtain an algebraic expansion of the recurrence relation corresponding to each sailor's transformation of the pile, ${\displaystyle n_{i}}$ being the number left by the sailor:

${\displaystyle n_{i}={\frac {m-1}{m}}(n_{i-1}-1)}$

where ${\displaystyle n_{i\rightarrow 0}\equiv N}$, the number originally gathered, and ${\displaystyle n_{i\rightarrow m}}$ the number left in the morning. Expanding the recurrence by substituting ${\displaystyle n_{i}}$ for ${\displaystyle n_{i-1}}$ ${\displaystyle m}$ times yields:

${\displaystyle n_{m}=\left({\frac {m-1}{m}}\right)^{m}\cdot n_{0}-\left[({\frac {m-1}{m}})^{m}+...+({\frac {m-1}{m}})^{2}+{\frac {m-1}{m}}\right]}$

Factoring the latter term,

${\displaystyle n_{m}=\left({\frac {m-1}{m}}\right)^{m}\cdot n_{0}-\left({\frac {m-1}{m}}\right)\cdot \left[({\frac {m-1}{m}})^{m-1}+...+{\frac {m-1}{m}}+1\right]}$

The power series polynomial in brackets of the form ${\displaystyle x^{m-1}+...+x+1}$ sums to ${\displaystyle (1-x^{m})/(1-x)}$ so,

${\displaystyle n_{m}=\left({\frac {m-1}{m}}\right)^{m}\cdot n_{0}-\left({\frac {m-1}{m}}\right)\cdot \left[\left(1-({\frac {m-1}{m}})^{m}\right){\bigg /}\left(1-({\frac {m-1}{m}})\right)\right]}$

which simplifies to:

${\displaystyle n_{m}=\left({\frac {m-1}{m}}\right)^{m}\cdot n_{0}-(m-1)\cdot {\frac {m^{m}-(m-1)^{m}}{m^{m}}}}$

But ${\displaystyle n_{m}}$ is the number left in the morning which is a multiple of ${\displaystyle m}$ (i.e. ${\displaystyle F}$, the number allotted to each sailor in the morning):

${\displaystyle m\cdot F=\left({\frac {m-1}{m}}\right)^{m}\cdot n_{0}-(m-1)\cdot {\frac {m^{m}-(m-1)^{m}}{m^{m}}}}$

Solving for ${\displaystyle n_{0}}$(=${\displaystyle N}$),

${\displaystyle N=m^{m}\cdot {\frac {m-1+m\cdot F}{(m-1)^{m}}}-(m-1)}$

The equation is a linear Diophantine equation in two variables, ${\displaystyle N}$ and ${\displaystyle F}$. ${\displaystyle m}$ is a parameter that can be any integer. The nature of the equation and the method of its solution do not depend on ${\displaystyle m}$.

Number theoretic considerations now apply. For ${\displaystyle N}$ to be an integer, it is sufficient that ${\displaystyle {\frac {m-1+m\cdot F}{(m-1)^{m}}}}$ be an integer, so let it be ${\displaystyle r}$:

${\displaystyle r={\frac {m-1+m\cdot F}{(m-1)^{m}}}}$

The equation must be transformed into the form ${\displaystyle ax+by=\pm 1}$ whose solutions are formulaic. Hence:

${\displaystyle (m-1)^{m}\cdot r-m\cdot s=-1}$, where ${\displaystyle s=1+F}$

Because ${\displaystyle m}$ and ${\displaystyle m-1}$ are relatively prime, there exist integer solutions ${\displaystyle (r,s)}$ by Bézout's identity. This equation can be restated as:

${\displaystyle (m-1)^{m}\cdot r\equiv -1\mod m}$

But (m–1)^m is a polynomial Z · m–1 if m is odd and Z · m+1 if m is even, where Z is a polynomial with monomial basis in m. Therefore r₀=1 if m is odd and r₀=–1 if m is even is a solution.

Bézout's identity gives the periodic solution ${\displaystyle r=r_{0}+k\cdot m}$, so substituting for ${\displaystyle r}$ in the Diophantine equation and rearranging:

${\displaystyle N=r_{0}\cdot m^{m}-(m-1)+k\cdot m^{m+1}}$

where ${\displaystyle r_{0}=1}$ for ${\displaystyle m}$ odd and ${\displaystyle r_{0}=-1}$ for ${\displaystyle m}$ even and ${\displaystyle k}$ is any integer.^[19] For a given ${\displaystyle m}$, the smallest positive ${\displaystyle k}$ will be chosen such that ${\displaystyle N}$ satisfies the constraints of the problem statement.

In the William's version of the problem, ${\displaystyle m}$ is 5 sailors, so ${\displaystyle r_{0}}$ is 1, and ${\displaystyle k}$ may be taken to be zero to obtain the lowest positive answer, so N = 1  · 5⁵ – 4 = 3121 for the number of coconuts in the original pile. (It may be noted that the next sequential solution of the equation for k=–1, is –12504, so trial and error around zero will not solve the Williams version of the problem, unlike the original version whose equation, fortuitously, had a small magnitude negative solution).

Here is a table of the positive solutions ${\displaystyle N}$ for the first few ${\displaystyle m}$ (${\displaystyle k}$ is any non-negative integer):

${\displaystyle m}$	${\displaystyle N}$
2	${\displaystyle 11+k\cdot 8}$[20]
3	${\displaystyle 25+k\cdot 81}$
4	${\displaystyle 765+k\cdot 1024}$
5	${\displaystyle 3121+k\cdot 15,625}$
6	${\displaystyle 233,275+k\cdot 279,936}$
7	${\displaystyle 823,537+k\cdot 5,764,801}$
8	${\displaystyle 117,440,505+k\cdot 134,217,728}$

Other variants and general solutions

Other variants, including the putative predecessor problem, have related general solutions for an arbitrary number of sailors.

When the morning division also has a remainder of one, the solution is:

${\displaystyle N=-(m-1)+k\cdot m^{m+1}}$

For ${\displaystyle m=5}$ and ${\displaystyle k=1}$ this yields 15,621 as the smallest positive number of coconuts for the pre-William's version of the problem.

In some earlier alternate forms of the problem, the divisions came out even, and nuts (or items) were allocated from the remaining pile after division. In these forms, the recursion relation is:

${\displaystyle n_{i}={\frac {m-1}{m}}n_{i-1}-1}$

The alternate form also had two endings, when the morning division comes out even, and when there is one nut left over for the monkey. When the morning division comes out even, the general solution reduces via a similar derivation to:

${\displaystyle N=-m+k\cdot m^{m+1}}$

For example, when ${\displaystyle m=4}$ and ${\displaystyle k=1}$, the original pile has 1020 coconuts, and after four successive even divisions in the night with a coconut allocated to the monkey after each division, there are 80 coconuts left over in the morning, so the final division comes out even with no coconut left over.

When the morning division results in a nut left over, the general solution is:

${\displaystyle N=r_{0}\cdot m^{m}-m+k\cdot m^{m+1}}$

where ${\displaystyle r_{0}=-1}$ if ${\displaystyle m}$ is odd, and ${\displaystyle r_{0}=1}$ if ${\displaystyle m}$ is even. For example, when ${\displaystyle m=3}$, ${\displaystyle r_{0}=-1}$ and ${\displaystyle k=1}$, the original pile has 51 coconuts, and after three successive divisions in the night with a coconut allocated to the monkey after each division, there are 13 coconuts left over in the morning, so the final division has a coconut left over for the monkey.

Other post-Williams variants which specify different remainders including positive ones (i.e. the monkey adds coconuts to the pile), have been treated in the literature. The solution is:

${\displaystyle N=r_{0}\cdot m^{m}-c\cdot (m-1)+k\cdot m^{m+1}}$

where ${\displaystyle r_{0}=1}$ for ${\displaystyle m}$ odd and ${\displaystyle r_{0}=-1}$ for ${\displaystyle m}$ even, ${\displaystyle c}$ is the remainder after each division (or number of monkeys) and ${\displaystyle k}$ is any integer (${\displaystyle c}$ is negative if the monkeys add coconuts to the pile).

Other variants in which the number of men or the remainders vary between divisions, are generally outside the class of problems associated with the monkey and the coconuts, though these similarly reduce to linear Diophantine equations in two variables. Their solutions yield to the same techniques and present no new difficulties.