Monkeys And Coconuts
May 8, 2015
Today’s exercise has a bit of a Project Euler feel to it. Solving the problem for five or six sailors is easy, but solving it for thirty sailors is hard unless you figure out the secret. Let’s start with a simple recursion that solves the problem by brute force, counting up until the solution is found:
(define (coconuts sailors)
(let loop ((nuts sailors) (left sailors)
(takes sailors) (result (list)))
(cond ((and (zero? takes) (zero? (modulo left sailors)))
(reverse (cons (list left (quotient left sailors) 0) result)))
((and (positive? takes) (= (modulo left sailors) 1))
(loop nuts (- left (quotient left sailors) 1) (- takes 1)
(cons (list left (quotient left sailors) 1) result)))
(else (loop (+ nuts 1) (+ nuts 1) sailors (list))))))
Sailors is the number of sailors in the puzzle, and never changes. Nuts is the number of coconuts in the starting pile, and increases by 1 each time a trial solution fails. Left is the number of coconuts left each time a sailor takes his share, reduced by one-nth minus 1 for each sailor. Takes is the number of times a sailor has taken coconuts from the pile, decreasing by 1 each time a sailor wakes up and restarting from the number of sailors at each trial. Result is a list of how many coconuts remain at the start of each taking, the number of coconuts taken, and the number of coconuts given to the monkey. Here are the results:
> (coconuts 5)
((3121 624 1) (2496 499 1) (1996 399 1) (1596 319 1)
(1276 255 1) (1020 204 0))
> (coconuts 6)
((233275 38879 1) (194395 32399 1) (161995 26999 1) (134995 22499 1)
(112495 18749 1) (93745 15624 1) (78120 13020 0))
I computed the output for the cases from 2 sailors to 8 sailors (it starts getting slow at that point) and went to OEIS, where I found sequence A002021 and the formula for computing the initial number of coconuts:
(define (coconuts n)
(if (odd? n)
(- (expt n n) n -1)
(* (- n 1) (- (expt n n) 1))))
And here’s the number of coconuts for each number of sailors up to thirty, which is computed in a blink of an eye:
> (map coconuts (range 31))
(0 1 3 25 765 3121 233275 823537 117440505 387420481
89999999991 285311670601 98077104930805 302875106592241
144456088732254195 437893890380859361 276701161105643274225
827240261886336764161 668888937280041138782191
1978419655660313589123961 1992294399999999999999999981
5842587018385982521381124401 7169985424648610705329581195243
20880467999847912034355032910545
30675922867556534862328873875406825
88817841970012523233890533447265601
153902989505178932769916857210005094375
443426488243037769948249630619149892777
894929124057841121289463662840844356943845
2567686153161211134561828214731016126483441
5970842830744820999999999999999999999999999971)
You can run the program at http://ideone.com/NXe7Ks. This puzzle caused quite a stir at the Saturday Evening Post when it was published on October 9, 1926 as part of a story by Ben Ames Williams; 2000 people wrote the magazine in the next week asking for the solution.
Programming Praxis 
Bruteforce in Python..
With all the stealing, better call them pirates..
3 25
4 765
5 3121
6 233275
7 823537
8 117440505
9 387420481
..
This site interests me. Are you collecting answers to problems? Can a robot solve these problems?
I am very put off by the way the questions are worded – “your task is to …”. It reminds me of lunatics who write on a blog demanding that people sent them answers to problems.
You can solve the difference equation and apply a divisibility condition to get a formula for the least number of coconuts:
We start with C coconuts and N sailors.
Let C_0 = C be the initial number of coconuts.
From the problem’s description, C_n = (C_n – 1) * (N – 1) / N, and this is a positive integer.
The final condition is that N | C_N.
The solution to the difference equation is C_n = (C+N-1)((N-1)/N)^N + 1 – N.
Since C_n needs to be an integer for each n, and hcf(N-1,N) = 1, we need N^n | (C+N-1), hence N^N | (C+N-1).
Rewrite to C+N-1 = kN^N for some integer k.
The final condition means that N | k(N-1)^N +1 – N.
Rewriting again, k(N-1)^N +1 -N ≡ 0 (mod N)
so k ≡ (-1)^(N-1) (mod N)
Choosing k to minimise C, then, k = 1 if N is odd, and N-1 if N is even.
So C = N^N -N +1 if N is odd, (N-1)N^N -N +1 if N is even.
I get 5.970842831×10^45 on my calculator for 30 sailors. Which is a lot of coconuts! But the monkey only gets 30 of them.
@namako – Nice.
I started with the number of coconuts in the morning (base) and worked backwards to see how many would be in the original pile (pile).
We know that base is divisible by the number of sailors (nsailors). We also know that it is divisible by nsailors-1, because the last sailor pile*(nsailors-1)/nsailors after he took his cut. So, base is a multiple of nsailors*(nsailors – 1).
To find the size of the pile before the sailor gave one to the monkey and took a cut: pile = pile * (nsailors) // (nsailors – 1) + 1. Each time, the pile must be divisible by nsailors – 1. If not, increase base and try again. Each time, I printed the base number of coconuts and the number of sailors before the test failed. Observing patterns in the printout, I figured out how to increase the step size fairly rapidly.
def how_many_coconuts(nsailors=5): seen = [None]*nsailors base = nsailors*(nsailors - 1) seen[0] = base step = base best = 0 while True: pile = base #print('\n', pile, end=' ') for sailor in range(nsailors): pile = pile * nsailors // (nsailors - 1) + 1 # note: // is integer division if pile % (nsailors - 1): #print(sailor, end=' ') if sailor > best: if seen[sailor]: step = base - seen[sailor] best = sailor #print(step, '<- new step', end=' ') else: seen[sailor] = base #print('<- first seen', end=' ') break else: return pile base += step print(how_many_coconuts(6))Another approach: we can find a Diophantine equation of the form Ax = By + C where x is the initial number of coconuts, and y is the number of coconuts given to each pirate at the end, and A, B and C are some constants depending on the number of pirates. So for 5 pirates we have 1024x = 15625y + 8404. We can solve such equations in a standard way using the extended Euclidean algorithm:
def egcd (a,b): x,y,z,w = 1,0,0,1 while b != 0: q,r = divmod(a,b) a,b = b,r x,y,z,w = z,w,x-q*z,y-q*w return a,x,y def monkey(n): A,B,C,m = 1,n,0,n-1 for i in range(n): # Ax = By + C where: # x is number of coconuts when i pirates are yet to chose A,B,C = m*A,n*B,n*C+m*A return A,B,C for n in range(1,31): A,B,C = monkey(n) # For A,B find Ax + By = d = gcd(A,B) (d,x,y) = egcd(A,B) assert(d == 1) # A and B are co-prime # Cx + kB is general solution, find smallest positive print(n,C*x%B)Rutgers solution is bad, only the first result is good:
java:
public int calcNumberOfCoconutsFor(int sailors) {
for (int i = sailors; i < 240000; i++) {
System.out.println(“current number: ” + i);
int remaining = i;
int withoutMonkeyShare = remaining – 1;
for (int j = 0; j < 5; j++) {
if (withoutMonkeyShare % sailors == 0) {
int oneOfFullPart = withoutMonkeyShare – withoutMonkeyShare / sailors;
if (((oneOfFullPart / (sailors – 1)) * sailors) % sailors == 0) {
remaining = oneOfFullPart;
withoutMonkeyShare = remaining – 1;
System.out.println(“remaining number: ” + remaining);
if (j == 4 && remaining % sailors == 0) {
return i;
}
}
}
}
}
return 0;
}
results:
5 – 3121
6 – 7771
7 – 16801