user
Five sailors are shipwrecked on an island and collect a large pile of coconuts during the day.

That night the first sailor wakes up and decides to take his first share early so tries to divide the pile of coconuts equally into five piles but finds that there is one coconut left over, so he tosses it to a monkey and then hides "his" one of the five equally sized piles of coconuts and pushes the other four piles together to form a single visible pile of coconuts again and goes to bed.

To cut a long story short, each of the sailors in turn gets up once during the night and performs the same actions of dividing the coconut pile into five, finding that one coconut is left over and giving that single remainder coconut to the monkey.

In the morning (after the surreptitious and separate action of each of the five sailors during the night), the remaining coconuts are divided into five equal piles for each of the sailors, whereupon it is found that the pile of coconuts divides equally amongst the sailors with no remainder. (Nothing for the monkey in the morning.)

The task

1. Calculate the minimum possible size of the initial pile of coconuts collected during the first day.
2. Use a method that assumes an answer is possible, and then applies the constraints of the tale to see if it is correct. (I.e. no applying some formula that generates the correct answer without integer divisions and remainders and tests on remainders; but constraint solvers *are* allowed.)
3. Calculate the size of the initial pile of coconuts if six sailors were marooned and went through a similar process (but split into six piles instead of five of course).
4. Show your answers here.

Extra credit (optional)

* Give some indication of the number of coconuts each sailor hides during the night.

Note

* Of course the tale is told in a world where the collection of any amount of coconuts in a day and multiple divisions of the pile, etc can occur in time fitting the story line, so as not to affect the mathematics.
* The tale is also told in a version where the monkey also gets a coconut in the morning. This is *not* that tale!

C.f

* Monkeys and Coconuts - Numberphile (Video) Analytical solution.
* A002021: Pile of coconuts problem The On-Line Encyclopedia of Integer Sequences. (Although some of its references may use the alternate form of the tale).
assistant
(formerly Perl 6)

**Works with**: rakudo version 2015.09

There is nowhere in the spec where it explicitly states that the sailors cannot equally share zero coconuts in the morning. Actually, The On-Line Encyclopedia of Integer Sequences A002021 considers the cases for 1 and 2 sailors equally sharing zero coconuts in the morning to be the correct answer.

This will test combinations of sailors and coconuts to see if they form a valid pairing. The first 6 are done using brute force, testing every combination until a valid one is found. For cases of 7 to 15 sailors, it uses a carefully crafted filter to drastically reduce the number of trials needed to find a valid case (to one, as it happens... :-) )

```
my @ones = flat 'th', 'st', 'nd', 'rd', 'th' xx 6;
my @teens = 'th' xx 10;
my @suffix = lazy flat (@ones, @teens, @ones xx 8) xx *;

# brute force the first six
for 1 .. 6 -> $sailors { for $sailors .. * -> $coconuts { last if check( $sailors, $coconuts ) } }

# finesse 7 through 15
for 7 .. 15 -> $sailors { next if check( $sailors, coconuts( $sailors ) ) }

sub is_valid ( $sailors is copy, $nuts is copy ) {
    return 0, 0 if $sailors == $nuts == 1;
    my @shares;
    for ^$sailors {
        return () unless $nuts % $sailors == 1;
        push @shares, ($nuts - 1) div $sailors;
        $nuts -= (1 + $nuts div $sailors);
    }
    push @shares, $nuts div $sailors;
    return @shares if !?($nuts % $sailors);
}

sub check ($sailors, $coconuts) {
    if my @piles = is_valid($sailors, $coconuts) {
        say "\nSailors $sailors: Coconuts $coconuts:";
        for ^(@piles - 1) -> $k {
             say "{$k+1}@suffix[$k+1] takes @piles[$k], gives 1 to the monkey."
        }
        say "The next morning, each sailor takes @piles[*-1]\nwith none left over for the monkey.";
        return True;
    }
    False;
}

multi sub coconuts ( $sailors where { $sailors % 2 == 0 } ) { ($sailors - 1) * ($sailors ** $sailors - 1) }
multi sub coconuts ( $sailors where { $sailors % 2 == 1 } ) { $sailors ** $sailors - $sailors + 1 }

```

Output:

```
Sailors 1: Coconuts 1:
1st takes 0, gives 1 to the monkey.
The next morning, each sailor takes 0
with none left over for the monkey.

Sailors 2: Coconuts 3:
...

Sailors 5: Coconuts 3121:
1st takes 624, gives 1 to the monkey.
2nd takes 499, gives 1 to the monkey.
3rd takes 399, gives 1 to the monkey.
4th takes 319, gives 1 to the monkey.
5th takes 255, gives 1 to the monkey.
The next morning, each sailor takes 204
with none left over for the monkey.

Sailors 6: Coconuts 233275:
1st takes 38879, gives 1 to the monkey.
2nd takes 32399, gives 1 to the monkey.
3rd takes 26999, gives 1 to the monkey.
4th takes 22499, gives 1 to the monkey.
5th takes 18749, gives 1 to the monkey.
6th takes 15624, gives 1 to the monkey.
The next morning, each sailor takes 13020
with none left over for the monkey.

Sailors 7: Coconuts 823537:
...

Sailors 15: Coconuts 437893890380859361:
...

```