数値を使わず 3 で割った余りを求める

お題

0 以上の整数が文字列として与えられ，それを 3 で割った余りを返す関数なりメソッドなりを定義せよ。この記事では Ruby を使うので，メソッドですね。

ただし，数値は一切使わないこととする。つまり，処理の途中で数値オブジェクトを使ったりしない。当然ながら返り値も文字列とする。

組込みのメソッドが内部で数値オブジェクトを生成していないか分からないので，自分で書いたコードが途中で数値オブジェクトを作っていなければよいことにする。

メソッド名を remainder_modulo_3 と名付けよう。英語が合ってるかよく分からんけど，remainder は剰余のことで，modulo 3 は「3 で割ったときの」という意味¹。

以下のようになればいい：

p remainder_modulo_3("0")  # => "0"
p remainder_modulo_3("8")  # => "2"
p remainder_modulo_3("12") # => "0"
p remainder_modulo_3("22") # => "1"

手でやる方法

プログラムを考える前に，手計算でやる方法を。

例えば 1234567 を 3 で割った余りは，ひと目見て 1 だと分かる。えっ？　どういうこと？

まず，もっと簡単な 87 を 3 で割った余りを考える。真面目に割り算をやってもいいのだが，もっとサボる方法がある。

\begin{eqnarray}
87 &=& 8 \times 10 + 7 \\
   &=& 8 \times (9 + 1) + 7 \\
   &=& 8 \times 9 + 8 + 7
\end{eqnarray}

なんだけれども，$8 \times 9$ は $9$ の倍数だから $3$ で割り切れる。よって，$8 \times 9$ は除外して考えてよくて，結局 $8 + 7$ を $3$ で割った余りを求めればよい。

$8 + 7$ は $15$ なので $3$ で割り切れる。余りは $0$ だ。

同じように考えると 1234567 のような大きな数だって，

\begin{eqnarray}
1234567 &=& 1 \times (999999 + 1) + 2 \times (99999 + 1) + 3 \times (9999 + 1) + 4 \times (999 + 1) + 5 \times (99 + 1) + 6 \times (9 + 1) + 7 \\
  &=& (9 の倍数) + 1 + 2 + 3 + 4 + 5 + 6 + 7
\end{eqnarray}

となるので，$1 + 2 + 3 + 4 + 5 + 6 + 7$ を $3$ で割った余りを求めればいい。

$1 + 2 + 3 + 4 + 5 + 6 + 7$ を真面目に計算する必要はなくて，

(1 + 2) + (3) + (4 + 5) + (6) + 7

のように $3$ の倍数が見えてるから，これらを除外して $7$ を $3$ で割った余りを求め，$1$ が得られる。

では $78932705$ のような数はどうか。この数の代わりに

7 + 8 + 9 + 3 + 2 + 7 + 0 + 5

を考えればいいのだが，これらの数字のうち，$9$，$3$，$0$ は $3$ の倍数だから除外してよくて，

7 + 8 + 2 + 7 + 5

を考えればよい。
また，$7 = 2 \times 3 + 1$ などを考えると，$7$ を $1$ に，$8$ を $2$ に，$5$ を $2$ に置き換えた

1 + 2 + 2 + 1 + 2

を考えればいいわけだ。（出てくる数字は 1 と 2 しかあり得ない）

人間ならこれをパッと見て $1$ を $2$ を組み合わせて $3$ を作って除外し，余りは $2$ だとすぐに分かる。
しかし，これをプログラムによる文字列処理をやるには？

やはりソートして

1 + 1 + 2 + 2 + 2

とし，"11222" という文字列を作るのがいいだろう。

あとは "111" とか "222" とか "12" などの文字列を削除していけばよさそうだ。

コード

こんなんできました：

def remainder_modulo_3(number)
  s = number.delete("0369").tr("4578", "1212")
    .chars.sort.join
    .gsub(/(.)\1\1|1122|12/, "")
  {"" => "0", "1" => "1", "11" => "2", "2" => "2", "22" => "1"}[s]
end

文字列で 0 以上の整数を与え，文字列で "0"，"1"，"2" のいずれかを返す。

ちょっと試してみよう：

1000000.times do |n|
  puts n unless (n % 3).to_s == remainder_modulo_3(n.to_s)
end

普通に Integer で計算したものと，remainder_modulo_3 メソッドで得たものを比較して，一致してなければそれを表示する。
やってみたところ何も表示されなかったので，コードは合っているようだ。

解説

ちょっとメソッドチェーンが長いけれども，やっていることは単純。

まず

delete("0369")

だが，0, 3, 6, 9 は 3 の倍数なので，これらの数字は除外する。

次の

tr("4578", "1212")

は，例えば 4 は 3 + 1 だから 1 に置き換えてよい，5 は 2 に置き換えてよい，ということ。

その次の

chars.sort.join

は，まず文字列を 1 文字ずつバラし，それをソートして再び繋げる。
これにより，例えば "212" から "122" が得られる。

この時点で得られる文字列は，「0 文字以上の "1" のあとに 0 文字以上の "2" が続く」というものになる。それ以外のパターンはあり得ない。

その次の

gsub(/(.)\1\1|1122|12/, "")

は，特定の文字列を左から順に削除しているのだが，正規表現がちょっとややこしい。

ハイライトは (.)\1\1 の部分。ここは後方参照を使っている。(.) でキャプチャーした文字がそのあとに二つ続くことを意味し，ここ全体としては「同じ数字が三つ並んだもの」にマッチする。

それから，"1" の列と "2" の列の境界部分に存在しうる "1122" と "12" にもマッチする。

これらを削除するわけだ。

この変換のあと得られる文字列はどんなものがありうるか。
ちょっと退屈だが，"1" の個数で場合分けしてみよう。

まず，"111" が真っ先に削除されるので（3 の倍数個の "1" が削除されるから）"1" の個数は 0, 1, 2 個の場合だけ考えればよいと分かる。

"1" が 0 個のとき，"2" が 0 個以上連なった文字列である。3 の倍数個の "2" が削除されることを思えば，""，"2"，"22" の三つがありうる。

次に "1" が 1 個のとき，うしろに続く "2" が 0 個なら "1" だし，"2" が 1 個なら全体（"12"）が削除されて "" になり，"2" が 2 個なら "2" となる。"2" が 3 個以上のときは "222" が削除されるので，考えなくてよい（可能性は尽きている）。つまり，"1"，""，"2" の三つがありうる。

最後に "1" が 2 個のとき，うしろに続く "2" が 0 個なら，"11" だし，"2" が 1 個なら "12" が削除されて "1" になるし，"2" が 2 個なら全体（"1122"）が削除されて空文字列になる。"2" が 3 個なら "1122" が削除されて "2" となる。4 個以上は考えなくてよい。つまり，"11"，"1"，""，"2" の四つがありうる。

ふぅ，めんどくさかった。

結局，変換後の文字列は

• ""
• "1"
• "11"
• "2"
• "22"

の五つの可能性しかない。

これらについての余りをハッシュで導いている。
以上。

応用

9 で割った余りも全く同様にできる。

2 や 5 で割った余りは最後の桁（1 の位）だけを見ればいい（10 が 2 や 5 で割り切れるから）。

4 で割った余りは最後の 2 桁を見る（100 が 4 で割り切れるから）。

8 で割った余りは最後の 3 桁を見る（1000 が 8 で割り切れるから）。

6 で割った余りはだいぶややこしいはず。いずれ挑戦してみたい。

7 で割った余りを数値オブジェクトを生成せずに求めることができるのかは，よく分からない。

最後に

「だからなに？」と言われても答えに窮する。
「整数論」のタグを付けておいたけど，そんな大したものじゃないし，実用性も無いし，すごく面白いというわけでもない。
なにげに思い立ってやってみただけ。

---

1. modulo 3 は，正式な数学の用語では「3 を法として」と言う。 ↩