3の倍数の正規表現の求め方

目次

• 序論

• 導出方法

序論

例えば、2の倍数は末尾が必ず偶数だから、/[02468]$/という正規表現で判定できる。また、5の倍数は末尾が0か5なので、/[05]$/で判定できる。このように一部の数の倍数は、文字列として正規表現で判定することができる。

それでは、3の倍数の場合はどうだろうか。

導出方法

3の倍数は、末尾の文字だけで判断することはできないが、全ての桁を足すと3の倍数になるという性質がある。

今、ある正規表現rが、別の正規表現sとaを使って、

r = s | ra （sまたはra）

と表せるとき、rは

r = sa* （sの後にaが0個以上）

と求められるという、Ardenの補題というものが存在する。

そこで、3を法として0、1、2と合同な数を表す正規表現をそれぞれa、b、c、[0369]を0、[147]を1、[258]を2で表すとすると、各桁の総和を3で割った余りと、その数自身を3で割った余りが一致することから、

a = a0 | b2 | c1
b = a1 | b0 | c2
c = a2 | b1 | c0

が成り立つ。Ardenの補題を使って、まず3つ目の式をcについて解くと、

c = a2 | b1 | c0
  = (a2 | b1) | c0
  = (a2 | b1)0*

これを2つ目の式に代入して、同様にbについて解くと、

b = a1 | b0 | c2
  = a1 | b0 | (a2 | b1)0*2
  = a1 | b0 | a20*2 | b10*2
  = a(1 | 20*2) | b(0 | 10*2)
  = a(1 | 20*2)(0 | 10*2)*

これらを1つ目の式に代入して、最後にaについて解くと、

a = a0 | b2 | c1
  = a0 | b2 | (a2 | b1)0*1
  = a0 | b2 | a20*1 | b10*1
  = a(0 | 20*1) | b(2 | 10*1)
  = a(0 | 20*1) | a(1 | 20*2)(0 | 10*2)*(2 | 10*1)
  = a(0 | 20*1 | (1 | 20*2)(0 | 10*2)*(2 | 10*1))
  = (0 | 20*1 | (1 | 20*2)(0 | 10*2)*(2 | 10*1))*

となり、a、b、cが全て消去できた。0、1、2はそれぞれ[0369]、[147]、[258]のことであったから、上記を通常の正規表現表記に戻すと、

a = /^(?:[0369]|[258][0369]*[147]|(?:[147]|[258][0369]*[258])(?:[0369]|[147][0369]*[258])*(?:[258]|[147][0369]*[147]))*$/

が得られる。

見ての通り、きわめて複雑なため、実際に3の倍数を判定する場合は、数値に変換して剰余を取る方がはるかに良い。なお、上記の正規表現では、先頭に0が連続するなど、整数としては不自然なものもマッチしてしまうので、その辺りを検出するには別のロジックが必要である。