「5と8を使った和で表すことができない最大の整数を求めよ」を数理計画的に解く

問題定義

「5と8を使った和で表すことができない最大の整数を求めよ」というツイートが話題ですね。

小2長男「算数の問題教えて。」
俺「いいよー。どんな問題？」
長男「5と8の和で表すことができない最大の整数を求めよ。」
俺「！？」

小4向けの問題集だけど大学入試で出てもおかしくないレベル。なかなか良問だった。

— 吉田匠 (@takuYSD) 2019年1月27日

解析的には$5×8-(5+8)=27$と一瞬で求まる（https://todai-counseling.com/?p=1430）わけですが、本記事ではこれを数理計画的なアプローチで解いてみます。

コードは以下のGithubに上げてあります。
https://github.com/karak/solve-elementary-math-problem

アルゴリズム

5の倍数と8の倍数の和で表される整数の集合を$S$とする。
このとき、以下の条件を満たす整数$k$を1から昇順に探索し、最初に見つかったものが解である。

1. $k \not \in S$
2. $k+i \in S\ (i=1..5)$

実装

JavaScript(ES6)で実装します。

メインルーチン

function solve() {
  /* ５の倍数と8の倍数の和で表される整数の集合Sを定義する */
  const S = new Set((i, j) => 5 * i + 8 * j);
  /* kがSに含まれており、k+1からk+5がSに含まれていないことを判定する関数 criteria を定義する */
  const isInS = k => S.includes(k);
  const criteria = k => !isInS(k) && all(k + 1, k + 5, isInS);
  /* criteria を満たす1以上の最小の整数を探索する。 */
  const solution = minimumNumberThatSatisfies(criteria);
  return solution;
}

アルゴリズムを素直に表現したコードにしてみました。そのために関数型のスタイルを多用しているので、HaskellやMLといった言語を使っている人の方が馴染みがあるかもしれません。

Set の実装

/**
 * 2つの0以上の整数i, jに対して整数を返す関数fによって定義される集合。
 * ただし、fはi,jに対して単調増加とする。
 */
class Set {
  constructor(f) {
    this.f = f;
  }

  /** 整数 k が集合に包含されているかを判定する。 */
  includes(k) {
    for (let i = 0; ; i += 1) {
      let j = 0;
      const y0 = this.f(i, j);
      if (y0 > k) {
        break;
      } else if (y0 === k) {
        return true;
      }
      for (j = 1; ; j += 1) {
        const yj = this.f(i, j);
        if (yj > k) {
          break;
        } else if (yj === k) {
          return true;
        }
      }
    }
    return false;
  }
}

Setのコンストラクタは2つの0以上の整数 $i, j$ を受け取って一つの整数を返す関数fを受け取ります。

Setは任意の整数$k$が集合に含まれるかどうかを判定するincludesというメソッドを持ちます。

includes は二重のforループによる単純な探索です。探索中の値が$k$を超えたら処理を止めるため、fは、$i, j$ いずれに対しても単調増加である必要があります（逆に、それさえ満たせば正しく動くルーチンになっています）。

効率化

上のやり方では一つの整数に対して5回判定処理が実行されるため、非常に無駄です。

よって、一度計算した値を使い回す（キャッシュする）ことにしましょう。

次のような高階関数¹ memoizeを定義します。

function memoize(f) {
  const cache = [];
  return function(k) {
    if (k >= cache.length) {
      for (let i = cache.length; i <= k; i += 1) {
        cache.push(f(i));
      }
    }
    return cache[k];
  };
}

今回は昇順に探索されることがわかっているので、計算済みの値より大きな数値がきたらその間の計算を一気に実行するように実装しています。

これを次のようにして Set に組み込めば完成です。

class Set {
  constructor(f) {
    this.f = f;
    this.includes = memoize(this.includes.bind(this));
  }
}

.bind(this)は関数が実行される際のthisが変わらないようにするためのものです。ここではそれ以上の解説はしません。

Appendix. 証明

一応。このアルゴリズムの正しさの雑な証明を記しておきます。

1. このような$k$があった場合、$k+5$以上の全ての数が表されることを示す。

まず

$$
\forall {k^\prime}\gt k+5;\exists j \in {\mathbb Z},|,{k^\prime}=k_i+5j\ (i = 1..5)
$$

である。

これを条件2を用いて展開すると

$$
{k^\prime}=k_i+5j=5(n+j)+8m
$$

となる。

ゆえに、${k^\prime} \in S$である。

1. このような$k$がなかった場合、解が存在しないことを示す。

対偶の命題「解が存在した場合は必ず該当の条件を満たす」ことを示せればよい。
これは自明である。

1. 関数を受け取って関数を返す関数。 ↩