Sailors, coconuts and a monkey problem: Difference between revisions
→{{header|Python}}: Link to blog. |
|||
Line 24: | Line 24: | ||
* [http://oeis.org/A002021 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). |
* [http://oeis.org/A002021 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). |
||
=={{header|C}}== |
|||
<lang c>#include <stdio.h> |
|||
int valid(int n, int nuts) |
|||
{ |
|||
int k; |
|||
for (k = n; k; k--, nuts -= 1 + nuts/n) |
|||
if (nuts%n != 1) return 0; |
|||
return !(nuts%n); |
|||
} |
|||
int main(void) |
|||
{ |
|||
int n, x; |
|||
for (n = 2; n < 10; n++) { |
|||
for (x = 0; !valid(n, x); x++); |
|||
printf("%d: %d\n", n, x); |
|||
} |
|||
return 0; |
|||
}</lang> |
|||
{{out}} |
|||
<pre> |
|||
2: 3 |
|||
3: 25 |
|||
4: 765 |
|||
5: 3121 |
|||
6: 233275 |
|||
7: 823537 |
|||
8: 117440505 |
|||
9: 387420481 |
|||
</pre> |
|||
=={{header|Python}}== |
=={{header|Python}}== |
||
You may want to read [http://paddy3118.blogspot.co.uk/2015/05/solving-monkey-and-coconuts-problem.html Solving the Monkey and coconuts problem] to get more background on the evolution of the Python code. |
You may want to read [http://paddy3118.blogspot.co.uk/2015/05/solving-monkey-and-coconuts-problem.html Solving the Monkey and coconuts problem] to get more background on the evolution of the Python code. |
Revision as of 06:12, 2 May 2015
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 tosses it to a monkey, he 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 gets up singly, 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 pile of coconuts are divided into five equal piles for each of the sailors and 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
- Calculate the minimum size of the initial pile of coconuts collected during the first day.
- Use a method that assumes an answer 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).
- 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).
- 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).
C
<lang c>#include <stdio.h>
int valid(int n, int nuts) { int k; for (k = n; k; k--, nuts -= 1 + nuts/n) if (nuts%n != 1) return 0; return !(nuts%n); }
int main(void) { int n, x; for (n = 2; n < 10; n++) { for (x = 0; !valid(n, x); x++); printf("%d: %d\n", n, x); } return 0; }</lang>
- Output:
2: 3 3: 25 4: 765 5: 3121 6: 233275 7: 823537 8: 117440505 9: 387420481
Python
You may want to read Solving the Monkey and coconuts problem to get more background on the evolution of the Python code.
Python: Procedural
<lang python>def monkey_coconuts(sailors=5):
"Parameterised the number of sailors using an inner loop including the last mornings case" nuts = sailors while True: n0, wakes = nuts, [] for sailor in range(sailors + 1): portion, remainder = divmod(n0, sailors) wakes.append((n0, portion, remainder)) if portion <= 0 or remainder != (1 if sailor != sailors else 0): nuts += 1 break n0 = n0 - portion - remainder else: break return nuts, wakes
if __name__ == "__main__":
for sailors in [5, 6]: nuts, wake_stats = monkey_coconuts(sailors) print("\nFor %i sailors the initial nut count is %i" % (sailors, nuts)) print("On each waking, the nut count, portion taken, and monkeys share are:\n ", ',\n '.join(repr(ws) for ws in wake_stats))</lang>
- Output:
For 5 sailors the initial nut count is 3121 On each waking, the nut count, portion taken, and monkeys share are: (3121, 624, 1), (2496, 499, 1), (1996, 399, 1), (1596, 319, 1), (1276, 255, 1), (1020, 204, 0) For 6 sailors the initial nut count is 233275 On each waking, the nut count, portion taken, and monkeys share are: (233275, 38879, 1), (194395, 32399, 1), (161995, 26999, 1), (134995, 22499, 1), (112495, 18749, 1), (93745, 15624, 1), (78120, 13020, 0)
Python: Recursive
<lang python>def wake_and_split(n0, sailors, depth=None):
if depth is None: depth = sailors portion, remainder = divmod(n0, sailors) if portion <= 0 or remainder != (1 if depth else 0): return None else: return n0 if not depth else wake_and_split(n0 - portion - remainder, sailors, depth - 1)
def monkey_coconuts(sailors=5):
"Parameterised the number of sailors using recursion including the last mornings case" nuts = sailors while True: if wake_and_split(n0=nuts, sailors=sailors) is None: nuts += 1 else: break return nuts
if __name__ == "__main__":
for sailors in [5, 6]: nuts = monkey_coconuts(sailors) print("For %i sailors the initial nut count is %i" % (sailors, nuts))
</lang>
- Output:
For 5 sailors the initial nut count is 3121 For 6 sailors the initial nut count is 233275