一万円を崩す方法(Haskell)

一万円を両替して崩す方法は何通りあるだろうか.ただし:
・百円玉,五百円玉,千円札を自由に(好きなだけ)使って良い.
・五百円記念硬貨は10枚までしか使えない.
・二千円札は2枚までしか使えない.

この問題は以前の千円を崩す方法(Haskell)の変種である.新しい要素は五百円記念硬貨(普通の五百円玉と区別される)と二千円札である.どちらも個数(枚数)に制限がある.

答えは1561通りになるはず.

以前の記事では組み合わせ的な考察だけから漸化式を導いて解いたが,今回は母関数を使わねば漸化式を導くことができなかった.

これを求めためのHaskellプログラムは次のようになる:

p n = if n < 0 then 0
      else if n `rem` 100 == 0 then 1
      else 0
q n | (n < 0) = 0
    | otherwise = p n + q (n-500)
r n | (n < 0) = 0
    | otherwise = q n + r (n-1000)
s n | (n < 0) = 0
    | otherwise = r n - r (n-5500) + s (n-500)
t n | (n < 0) = 0
    | otherwise = s n - s (n-6000) + t (n-2000)

問題の答えは t 10000として求まる.

ブログに数式を書くのが面倒になったので,数列を母関数を通して扱う話からはじめて,このプログラムを導く過程をPDFにまとめてみた.(文字を大きくしておいたのでスマホでも読めると思う):数列と母関数

広告

切手を貼る方法(Haskell)

■問題:2セント,4セント,6セント,8セントの切手を封筒に一列に貼って10セントにしたい.何通りの方法があるか?(異なる並べ方は違う方法としてカウントする).

■注意:つまり「2,2,4,2」と「4,2,2,2」は違う方法としてカウントされる.

■問題出典:Pólya & Szegöの “Problems and Theorems in Analysis I”の問題3である.

{b_n}によって,『{n}セントを支払う方法の数』を表す.組み合わせについての簡単な考察により

{b_0 = 1.}
・負の添字に対して {b_n = 0.}
{b_n = b_{n-2} + b_{n-4} + b_{n-6} + b_{n-8}.}

がわかる.これを素直にHaskellのコードに移すと:

b :: Int -> Int
b n | (n < 0) = 0
    | (n ==0) = 1
    | otherwise = b (n-2) + b (n-4) + b (n-6) + b (n-8)

となる.よって b 10 を求めればよい.

$ ghci
Prelude> :l b.hs
[1 of 1] Compiling Main             ( b.hs, interpreted )

Ok, modules loaded: Main.
*Main> b 10
15

答えは15通りである.

■ Pólya & Szegöの “Problems and Theorems in Analysis I” では,さらに数列 {b_n}の母関数の閉じた式が扱われている.(今回は必要ないので扱わない.)

32ビット?64ビット?(自分用メモ)

■gccが32ビットか64ビットか:
gcc -v の出力の Target: のところを見る.

32ビットの場合 Target: mingw32
64ビットの場合 Target: x86_64-pc-msys

などのようになる.システムの細かな差異によって文字列は少しずつ違うが,64ビットの場合 x86_64 が部分文字列としてしばしば含まれる.

■ghcが32ビットか64ビットか:
次のようなファイルを作る:

main = print ()

そして

$ ghc --make foo.hs
[1 of 1] Compiling Main             ( foo.hs, foo.o )
Linking foo.exe ...

$ file foo.exe

32ビットの場合には
PE32 executable (console) Intel 80386, for MS Windows

64ビットの場合には 
PE32+ executable (console) x86-64, for MS Windows

のようになる.

■おまけ:
自分がどの gcc を使ってるのかわからなくなった場合などは
which -a gcc
すればよい.使い分けをしたい場合は適宜 .bashrc に alias を張ればよさそう.

HaskellからFFIでCの配列を扱う(マーシャリング)

HaskellのFFIについてはこのブログでも例えばこんな記事で扱っている.

今回はその記事では触れなかったマーシャリングについて扱う.まずは次のようなCの関数があったとしよう:

#include <stdlib.h>
#include <stdio.h>
#include "c_header.h"

/*
int sum(int* p);

int fib(int** pp, int n);
*/

int sum(int* p, size_t n)
{
  if(n == 0){ return 0; }
  size_t i;
  int retval = 0;
  for(i = 0; i < n; ++i)
  {
    retval += p[i];
  }
  return retval;
}

int fib(int** pp, int n)
{
  if(n<=0){ return 1;}
  *pp = malloc(n * sizeof(int));
  if(n>=1){ (*pp)[0] = 1;}
  if(n>=2){ (*pp)[1] = 1;}
  if(n>=3){
    int i;
    for(i=2; i < n; ++i)
    {
      (*pp)[i] = (*pp)[i-1] + (*pp)[i-2];
    }
  }
  return 0;
}

これらのコードは次のように使われる:

#include <stdio.h>
#include <stdlib.h>
#include "src/c_header.h"

#define N 10
int main(void)
{
  int array[] = {1,2,3,4,5,6,7,8,9,10};

  int s = sum(array, sizeof(array)/sizeof(array[0]));
  printf("sum=%d\n",s);

  int* p = 0;
  int r = fib(&p,N);
  if(r==1){ printf("failed"); }
  else{
    int i;
    for(i=0; i < N; ++i)
    {
      printf("fib(%d)=%d\n",i,p[i]);
    }
  }
  free(p);
  return 0;
}

sumやfibは次のようにHaskellから扱える:

module Lib
    where

import Foreign.C.Types
import Foreign.Ptr
import Foreign.Marshal.Array
import Foreign

-- int sum(int* p, size_t n);
foreign import ccall "c_header.h sum" cSum
  :: Ptr CInt -> CSize -> IO CInt

hSum :: [Int] -> IO Int
hSum xs =
  let
    xs' = fromIntegral <$> xs :: [CInt]
    len   = fromIntegral $ length xs :: CSize
  in
  do
    arr <- newArray xs' :: IO (Ptr CInt)
    l <- return len  :: IO CSize
    ret <- cSum arr l :: IO CInt
    return $ fromIntegral ret

-- int fib(int** pp, int n);
foreign import ccall "c_header.h fib" c_fib
  :: Ptr (Ptr CInt) -> CInt -> IO CInt

hFib :: Int -> IO [Int]
hFib n =
    do
      ptrOut <- malloc  :: IO (Ptr (Ptr CInt))
      n' <- return $ fromIntegral n :: IO CInt
      ret <- c_fib  ptrOut  n' :: IO CInt
      out <- peekArray n =<< peek ptrOut :: IO [CInt]
      free =<< peek ptrOut
      free ptrOut
      return (fromIntegral <$> out) :: IO [Int]

cSum と hSum, c_fibとhFibのシグネチャは結構ずれている.
関数cSumは sum と同様にポインタとサイズを受け取る.hSum ではサイズを配列から計算しているので長さを引数にする必要がない.
また,c_fib では二重ポインタと長さを引数にしているが,hFibでは長さだけが引数となっている.c_fib の引数となっている二重ポインタは出力用の変数だからである.

次のコードはhSum,hFibの使用例である.

module Main where

import Lib

main :: IO ()
main =
  do
    a <- hSum [1,2,3,4]
    print a
    xs <- hFib 15
    print xs

stack でこのコードをビルドする場合,stack.yaml に次のような行を加えねばならない:

c-sources:  src/c_impl.c

optparse-generic (Haskell)

自分用メモ.

必要なことはすべて https://github.com/Gabriel439/Haskell-Optparse-Generic-Library から辿れるhttp://hackage.haskell.org/package/optparse-generic/docs/Options-Generic.htmlに載っている.

■optparse-genericとは何ですか?:コマンドライン引数を処理するライブラリの一つです.

■インストール:stack install optparse-generic

■サンプル:

{-# LANGUAGE DataKinds          #-}
{-# LANGUAGE DeriveGeneric      #-}
{-# LANGUAGE FlexibleInstances  #-}  -- One more extension.
{-# LANGUAGE OverloadedStrings  #-}
{-# LANGUAGE StandaloneDeriving #-}  -- To derive Show
{-# LANGUAGE TypeOperators      #-}

import Options.Generic --stack install optparse-generic

data OptionInput  w = OptionInput
  { foo :: w ::: Int            <?>"Documentation for the foo flag"
  , bar :: w ::: Double         <?>"Documentation for the bar flag"
  , baz :: w ::: String         <?>"Documentation for the baz flag"
  , qux :: w ::: Maybe String   <?>"Documentation for the qux flag"
  , quux :: w ::: Bool          <?>"Documentation for the quux flag"
  } deriving (Generic)

instance ParseRecord (OptionInput Wrapped)
deriving instance Show (OptionInput Unwrapped)

main = do
    x <- unwrapRecord "program short description"
    let i = foo x :: Int
    let d = bar x :: Double
    let s = baz x :: String
    let s' = qux x :: Maybe String
    let b = quux x :: Bool
    print (x :: OptionInput Unwrapped)

■サンプルのビルド:stack ghc optiontest.hs
必要に応じて,package.yaml で
dependencies:
– optparse-generic

■サンプルを動かす:optiontest.exe --foo 2 --bar 3.478 --baz "hoge" --qux "fuga"

uniq 的な関数(Haskell)

Haskell のリストから重複要素を除去する関数はnubである.「同じかどうか」を判定する関数を引数に取る nubBy を使いたい場合もある.これらの関数はリスト全体を舐めて重複要素を除去する.

扱っている配列がソート済みである場合も多い.その場合,隣接要素だけ見ていけば重複要素を除去できるはずである.そうすれば少しだけ効率が良いかも知れない.そう考えてこんな関数を書いてみた:

uniq :: (Eq a) => [a] -> [a]
uniq = foldr  uniqAux []
  where uniqAux :: (Eq a) => a -> [a] -> [a]
        uniqAux t [] = [t]
        uniqAux t (u:us) = (if t == u then [u] else [t,u]) ++ us

uniqBy を作るのも簡単である.

※効率がどうこうと言ったが,性能比較はまだしていない.

千円を崩す方法(Haskell)

次のような問題を考えてみましょう:

千円を両替して崩す方法は何通りあるだろうか.ただし,一円玉,五円玉,十円玉,五十円玉,百円玉,五百円玉を自由に(好きなだけ)使って良いものとする.

まず問題を一般化し,つぎのように考えます.{A_n}によって「{n}円を一円玉で崩す方法の数」を表すことにします.(と言っても{n\ge 0}ならば常に{A_n = 1}なのですが).

また,{B_n}によって「{n}円を一円玉と五円玉で崩す方法の数」を,

{C_n}によって「{n}円を一円玉と五円玉と十円玉で崩す方法の数」を,

{D_n}によって「{n}円を一円玉と五円玉と十円玉と五十円玉で崩す方法の数」を,

{E_n}によって「{n}円を一円玉と五円玉と十円玉と五十円玉と百円玉で崩す方法の数」を,

最後に{F_n}によって「{n}円を一円玉と五円玉と十円玉と五十円玉と百円玉と五百円玉で崩す方法の数」を表すことにします.

このように定式化すると,クイズの答えは{F_{1000}}と表されます.あとはこの具体的な数値を求めれば良いわけです.

さて,{F_n}はを「n円を五百円玉を一枚も使わないで表した場合の数」と「(n-500)円をすべてのコインを好きなだけ使って表した場合の数」の和だと考えられます.
(追記2018/08/27 少し説明を補います.{n}円を全てのコインを使って崩した場合を全て列挙した集合を{X}としましょう.{X}を (i)五百円玉を一つも含まないもの (ii)少なくとも1枚の五百円玉を含むもの に分割できます.それぞれの場合からなる集合を{X_1,X_2}としましょう.{X = X_1 + X_2} (非交和)ですから,{|X| = |X_1| + |X_2|} となります.明らかに{|X_1| = E_n}です.{X_2}の全ての要素から五百円玉を一つ抜くと,それぞれは{n-500}円を崩したものになっています.したがって{|X_2| = F_{n-500}}です.
).よって

{F_n = E_n + F_{n-500}}

となります.よって,{F_n}の計算を{E_{n},\,F_{n-500}}の計算に還元できます.

同様に考えれば
{E_n = D_n + E_{n-100}}などの式が得られます.ただし,負のインデックスに対しては{A_n, B_n, C_n, D_n, E_n, F_n}はいずれもゼロとします.この考えをそのままHaskellコードにすれば次のようになります:

fA n | (n < 0) = 0
     | otherwise = 1

fB n | (n < 0) = 0
     | otherwise = fA n + fB (n-5)

fC n | (n < 0) = 0
     | otherwise = fB n + fC (n-10)

fD n | (n < 0) = 0
     | otherwise = fC n + fD (n-50)

fE n | (n < 0) = 0
     | otherwise = fD n + fE (n-100)

fF n | (n < 0) = 0
     | otherwise = fE n + fF (n-500)

これらの定義を書いてGHCiで:l 1000yen.hs してやってから fF 1000 を計算させると248908という答えが得られます.

したがって,一円玉,五円玉,十円玉,五十円玉,百円玉,五百円玉を自由に(好きなだけ)使って千円を両替する方法は全部で248908通りあることになります.

この問題はポリア他『組合せ論入門』p.11(近代科学社)で扱われている問題を改変したものです.(元の問題は1ドルを1セント,5セント,10セント,25セント,50セントで崩す問題です.)この問題はポリアのお気に入りだったのか,Pólya & Szegö “Problems and Theorems in Analysis I” にも収録されています.)

この記事では漸化式を組み合わせ論的な考えで導きましたが,ポリアの本では母関数を利用して漸化式を導いています.興味のある方は是非ポリアの『組合せ論入門』を読んでみてください.

Haskell の QuickCheck を自動化する

ライブラリを開発していると、複数のテストを一挙に回したくなるかもしれませんね。そんなときはこうします。

{-# LANGUAGE TemplateHaskell #-}

import Data.List
import Test.QuickCheck

-- 与えられた2つのリストを連結する
cat :: (Eq a) => [a] -> [a] -> [a]
cat [] ys = ys
cat (x:xs) ys = x : (xs `cat` ys)

-- cat が結合律を満たすかどうかのテスト
prop_cat xs ys zs = (xs `cat` ys) `cat` zs == xs `cat` (ys `cat` zs)

-- 最初のリストから二番目のリストの要素を除去したリストを作る
sub :: (Eq a) => [a] -> [a] -> [a]
sub [] ys = []
sub (x:xs) ys | x `elem` ys = xs `sub` ys
| otherwise = x : (xs `sub` ys)

-- sub が結合律を満たすかどうかのテスト
prop_sub xs ys zs = (xs `sub` ys) `sub` zs == xs `sub` (ys `sub` zs)
--to run this test, > quickCheck prop_cap

--最初のリストに含まれている要素を除外しつつ2つの与えられたリストをマージする
ucat :: (Eq a) => [a] -> [a] -> [a]
ucat [] ys = ys
ucat (x:xs) ys | x `elem` ys = x : (xs `ucat` (ys `sub` [x]))
| otherwise = x : (xs `ucat` ys)

-- ucat が結合律を満たすかどうかのテスト
prop_ucat xs ys zs = (xs `ucat` ys) `ucat` zs == xs `ucat` (ys `ucat` zs)

return []
main = $forAllProperties (quickCheckWithResult stdArgs { maxSuccess = 2000 })

■動かし方/その出力例

$ stack runghc qc.hs
Run from outside a project, using implicit global project config
=== prop_cat from qc.hs:12 ===
+++ OK, passed 2000 tests.

=== prop_sub from qc.hs:20 ===
*** Failed! Falsifiable (after 9 tests and 7 shrinks):
[0]
[]
[0]

=== prop_ucat from qc.hs:29 ===
+++ OK, passed 2000 tests.

■コードの解説
cat, sub, ucat というリスト演算を定義し、それらが結合法則を満たすかどうかチェックしています。テストの結果、cat は合格、subは失格(つまり結合法則の反例が見つかった)、ucatは合格となりました。

■ポイント
1. TemplateHaskell を使う。
2. テストの名前は prop_ で始まる。 (TemplateHaskellを使っていることからの制約)
3. return[] とかいうキモいやつは我慢。 (TemplateHaskellを使っていることからの制約)
4. main は一番最後に来る。 (TemplateHaskellを使っていることからの制約)

QuickCheckで100回以上テストを回す(メモ)

HaskellにはQuickCheckという便利なライブラリがあります。これは、自分で作った関数が特定の性質を満たしているかどうか手早くテストするときに役に立ちます。

たとえば、あなたが(多分自分の勉強のために)2つのリストを結合する関数myconcatを次のように書いたとしましょう:

import Test.QuickCheck
-- $ stack install QuickCheck

myconcat :: (Eq a) => [a] -> [a] -> [a]
myconcat [] ys = ys
myconcat (x:xs) ys = x : (xs `myconcat` ys)

実際これは多くのHaskell教科書に(++)の参照実装として挙げられているものをそのまま真似ただけですから、当然

(xs `myconcat` ys) `myconcat` zs == xs `myconcat` (ys `myconcat` zs)

という性質は「常に」成り立つと期待したいところです。このような事を保証するためには、結局なんらかの証明を与える必要があります。
例えば Richard Bird 著/山下伸夫 訳『関数プログラミング入門 — Haskellで学ぶ原理と技法』では、そのような証明を「手で」つける例が随所で扱われています。あるいは、Coqのような言語を使って、成り立っていることが期待される性質が実際に成り立つことの形式的な証明を与えるという手段もあります。

いずれにせよ、何かのしっかりとした証明をつけるというのはなかなか面倒なことではあります。そこで、乱数で生成した例で手っ取り早くテストしたいという場合があります。特に、「期待される性質」が実際に成り立っていないかもしれないという疑念があるときにはこのような検査は有効です。間違った命題—その命題が本当に間違っているかどうかを事前に知ることができない場合が多いことが厄介なわけですが—を証明しようとあれこれ悩みたくないですからね。

今の場合ならソースコードの末尾にこんな関数を付け加えておけば良いです:

mytest xs ys zs = (xs `myconcat` ys) `myconcat` zs == xs `myconcat` (ys `myconcat` zs)

そしてghciから

*Main> quickCheck mytest
+++ OK, passed 100 tests.

と試せば良いわけです。

ところで、100回以上テストしたい場合はどうすればいいのでしょうか? ここ(stackoverflow)で答を見つけました。答から先に書くと、たとえば5000回テストしたい場合には

*Main>quickCheckWith stdArgs { maxSuccess = 5000 } mytest

とすればいいです。

引用した stackoverflow のあるコメントの後半に「どうやってこの答をみつけたか」の丁寧な解説があったので補足しつつ翻訳します。

1.API documentation を見に行く

API documentation のページはこんなふうなリンクから飛べる

2. quickCheck を見てその次に見たのは maxSuccess フィールドを持つ Args 型だった。

Args型

3. 全部のフィールドを書くのは嫌だったので、Args 型の値を探したら stdArgs が見つかった。(ブラウザの検索機能 Ctrl+F を使いましょう)。または、hoogle を使っても良かったかもしれない。

4. 自分の Args 型変数を使いたいので検索を続行した。次の行に quickCheckWith があった—これだ! または、hoogleを使うという手もあった。

img3

「使ったことがないライブラリをどう使うか」というのは非常に重要です。上に書いてあることはHoogleを使い慣れている人が当たり前にやっていることでしょうが、きちんと段階化し言語化してあるところが素晴らしいと思って訳してしまいました。

更に補足すると、stdArgs { maxSuccess = 5000 }の箇所は、stdArgsが返すArgs型の値の maxSuccessフィールドを 5000 に書き換えた値を生成しているのでした。

Maybeの(>=>)を使って問題を解く

■マーティン・ガードナーのパズル本を見ていたらこんな問題が載っていた:

5人の男と一匹の猿が難破して無人島に漂着した。1日目、彼らは食糧としてたくさんのココナツを集めて回った。そしてその夜、すべてのココナツを積み上げて彼らは眠りについた。
 しかし全員が眠りについたあと、1人の男がふと目を覚ました。朝になってココナツを分けるとき、ひと悶着起きるかもしれないではないか。心配になった彼は自分の取り分を先取りしようと考えた。彼がココナツを5つの山に等分してみると、1つ余ったので、彼はそれを猿にあげてから、自分の取り分を隠して、残りを元通りに積んでおいた。
 しばらくして別の男が目を覚まして、同じことを考えた。やはりココナツは1つ余り、それは猿のものになった。こうして5人の男たちが順番に同じことをした。つまり1人ずつ目を覚ましては、ココナツの山を5つに分けて、残った1つを猿にあげて、自分の取り分を画した。朝になり、残ったココナツ全部を分けると、今度はきれいに5等分された。
(略) さて、最初にココナツはいくつあったのだろうか?

計算機で総当りしてももちろんこの問題は解ける。本には、これを少ない労力で解くためのトリックが紹介されていた。(「ガードナーの数学娯楽」/日本評論社)。そのトリックについてはこの記事では触れない。

この問題を見たとき、HaskellのMaybeモナドを使ったら素直に解けそうだと感じた。(そして実際に解けた)。ココナツの数をNとすると
N = 5A +1 ;  4A個の山を残す # 1人目の男
4A = 5B + 1 ; 4B個の山を残す # 2人目の男
4B = 5C + 1 ; 4C個の山を残す # 3人目の男
4C = 5D + 1 ; 4D個の山を残す # 4人目の男
4D = 5E +1 ; 4E個の山を残す # 5人目の男
4E = 5F ; きれいに5等分された
のようになる。「与えられた数から1を引いておけば5で割り切れる」という状況が続き、そうして得られた商の4倍だけ残すという操作が5回行われている。そこでこんな関数を考えてみよう:

g :: Int -> Int -> Maybe Int
g r n
    |  (n-r) `rem` 5 == 0  = Just( ((n-r) `quot` 5) * 4 )
    |  otherwise           = Nothing

こうすると、それぞれの男が行った操作は g 1 として表現できる:

g 1 :: Int -> Maybe Int

一般に、モナドMに対して X -> M Yの形の関数は、(>=>)で合成できるのだった。
(この記事では説明しないし、知っている必要もないが、この形の関数はこのモナドの与えるKleisli圏の射とみなす事ができ、(>=>)はこのタイプの射の「合成」とみなせるのだった)。

よって、5人の男がココナツに対して行った操作とその結果は

f :: Int -> Maybe Int
f = g 1 {- 1人目の男 -} >=> g 1{- 2人目の男 -} >=> g 1{- 3人目の男 -} >=> g 1{- 4人目の男 -} >=> g 1{- 5人目の男 -} >=> g 0

として表せる。もちろんこれはもっとコンパクトに

f = foldl1 (>=>) [g 1, g 1, g 1, g 1, g 1, g 0]

と書いてもいいし、さらにこれは

f = foldl1 (>=>) $ map g [1,1,1,1,1,0]

と書いてもいい。こうして得られたfInt -> Maybe Int という型を持つ。元のクイズの答をNとするとき、 f N Just ...という形をしているはずである。そこで、こんな関数を用意してみよう:

--  f の答がNothing ではない場合の引数を得るように変形する
getJustArg :: (a -> Maybe b) -> (a -> Maybe a)
getJustArg f x
    | isJust (f x)  = Just x
    | otherwise     = Nothing

この関数を使えば、問題のNは map (getJustArg f) [1 ..] というリストに含まれる「Just x」の形をした最初の元から得られることがわかる。Data.List の

find :: (a -> Bool) -> [a] -> Maybe a

を使えば最初の元を取ってこられそうだ。findMaybeをかぶせて返してくるおかげで、
find isJust (map (getJustArg f) [1 ..])Maybe(Maybe Int) 値になる。そこで join してMaybe を一段に落としてやると、得られる答は Just n の形をしているので fromJustInt値を引っ張り出せる:

fromJust . join $ find isJust (map (getJustArg f) [1 ..])

以上をまとめると次のようなプログラムが得られる:

import Control.Monad
import Data.List
import Data.Maybe

g :: Int -> Int -> Maybe Int
g r n
    |  (n-r) `rem` 5 == 0  = Just( ((n-r) `quot` 5) * 4 )
    |  otherwise           = Nothing

f = foldl1 (>=>) $ map g [1,1,1,1,1,0]

getJustArg :: (a -> Maybe b) -> (a -> Maybe a)
getJustArg f x
    | isJust (f x)  = Just x
    | otherwise     = Nothing

main = do{
  print $ fromJust . join $ find isJust (map (getJustArg f) [1 ..])
  }

答は3121となる。

■まとめ
Maybeモナドに対するKleisli射の合成演算(>=>)を用いてクイズを解いてみた。

■おまけの問題

5人の男と一匹の猿が難破して無人島に漂着した。1日目、彼らは食糧としてたくさんのココナツを集めて回った。そしてその夜、すべてのココナツを積み上げて彼らは眠りについた。
 しかし全員が眠りについたあと、1人の男がふと目を覚ました。朝になってココナツを分けるとき、ひと悶着起きるかもしれないではないか。心配になった彼は自分の取り分を先取りしようと考えた。彼がココナツを5つの山に等分してみると、4つ余ったので、彼は余ったココナツを猿にあげてから、自分の取り分を隠して、残りを元通りに積んでおいた。
 しばらくして別の男が目を覚まして、同じことを考えた。今度は3つ余ったので、彼はやはり余ったココナツを猿に与え、自分の取り分を隠してから残りを積んでおいた。
三番目の男も同じことを考えたが、彼がココナツを5つの山に分けようとすると今度は2つ余った。やはり彼は余ったココナツを猿に与え、自分の取り分を隠してから残りを積んでおいた。
四番目の男も同じことを考えたが、彼がココナツを5つの山に分けようとすると今度は1つだけ余った。やはり彼は余ったココナツを猿に与え、自分の取り分を隠してから残りを積んでおいた。
五番目の男も同じことを考えたが、彼だけは仲間を裏切ることを恥ずかしく思い、結局何もしなかった。
朝になり、残ったココナツ全部を分けると、きれいに5等分された。
さて、最初にココナツはいくつあったのだろうか?

最小の答は3089個になるはずである。