37.50.48

%20 の ブログ

3の倍数を正規表現で

leading zero を許容しない十進非負整数は、

/^(0|[1-9][0-9]*)$/

と表現できる。これは、

/^(0|([1-9]0*)+)$/

と表現することもできる。

 

以下では、「数」は「 leading zero を許容しない十進非負整数」と同じ意味で扱う。

 

「 x が 3 の倍数である」と「 x の各桁の数字の和が 3 の倍数である」が同値であることは知られている。
ということは、「 3 の倍数の後ろに 3 の倍数の繋げたもの」も 3 の倍数である。
ということは、3 の倍数全体の集合を正規表現で表現できるはずである。

できた。

/^(0|(([147][0369]*([147][0369]*[258][0369]*)*([147][0369]*[147]|[258])|[258][0369]*([258][0369]*[147][0369]*)*([147]|[258][0369]*[258])|[369])0*)+)$/

 

いきなり結果だけ見せられても分からないので、単純なところから考える。

1 または 2 のみからなる数について考える。

  • 111 は 3 の倍数である。
  • 12 は 3 の倍数である。
  • 21 は 3 の倍数である。
  • 222 は 3 の倍数である。

よって、これらを 1 回以上繰り返したものは 3 の倍数である。

/^(111|12|21|222)+$/

少し変形しておく。

/^(1(11|2)|2(1|22))+$/

3 の倍数であるが上記に該当しないものについて考える。

/^(1(【A】)*(11|2)|2(【B】)*(1|22))+$/

【A】が 3 の倍数ならば、1【A】11 は 3 の倍数である。

  • 【A】が 111 のとき、1【A】11111111 となり、先頭から見て 111111 に分けることができるので考えなくて良い。
  • 【A】が 12 のとき、1【A】1111211 となり、先頭から見て分けられないのでこれについて考えれば良い。
  • 【A】が 21 のとき、1【A】1112111 となり、先頭から見て 12111 に分けることができるので考えなくて良い。
  • 【A】が 222 のとき、1【A】11122211 となり、先頭から見て 122211 に分けることができるので考えなくて良い。

【A】は 12、同様にして【B】は 21 と分かる。

よって、1 または 2 のみからなる数で、3 の倍数であるもの全体は、

/^(1(12)*(11|2)|2(21)*(1|22))+$/

と表現できる。

ここに 3 を加えると、

/^(13*(13*23*)*(13*1|2)|23*(23*13*)*(1|23*2)|3)+$/

ここに 0 を加えると、

/^(0|((1[03]*(1[03]*2[03]*)*(1[03]*1|2)|2[03]*(2[03]*1[03]*)*(1|2[03]*2)|3)0*)+)$/

ここに 4, 5, 6, 7, 8, 9 を加えると、

/^(0|(([147][0369]*([147][0369]*[258][0369]*)*([147][0369]*[147]|[258])|[258][0369]*([258][0369]*[147][0369]*)*([147]|[258][0369]*[258])|[369])0*)+)$/

となる。