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】11
は111111
となり、先頭から見て111
と111
に分けることができるので考えなくて良い。 - 【A】が
12
のとき、1【A】11
は11211
となり、先頭から見て分けられないのでこれについて考えれば良い。 - 【A】が
21
のとき、1【A】11
は12111
となり、先頭から見て12
と111
に分けることができるので考えなくて良い。 - 【A】が
222
のとき、1【A】11
は122211
となり、先頭から見て12
と2211
に分けることができるので考えなくて良い。
【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*)+)$/
となる。