3で割り切れる2進数を表す正規表現

Lingrの「じょうほうかがく！」部屋で「3で割り切れる2進数を表す正規表現」が話題になって解いてみたので備忘録として記事にします。
※ この部屋はパスワード必須なので知っている方しか入れません。

「3で割り切れる2進数を表す正規表現」の解は以下のようになりました。

^(0*(
| 1 (00|11)* 01 (00|11)* 01
| 1 (00|11)* 01 (00|11)* 10 (00|11)* 10
| 1 (00|11)* 01 (00|11)* 10 (00|11)* 01 (00|11)* 01
| 1 (00|11)* 10
|01 (00|11)* 01 (00|11)* 01
|01 (00|11)* 01 (00|11)* 10 (00|11)* 10
|01 (00|11)* 01 (00|11)* 10 (00|11)* 01 (00|11)* 01
|01 (00|11)* 10
|10 (00|11)* 01
|10 (00|11)* 10 (00|11)* 01 (00|11) * 01
|10 (00|11)* 10 (00|11)* 10
|11
))\+$

この解を導くまでの考え方を簡単に説明すると、

1. 2進数文字列を左から2桁ずつに区切って、その合計が3の倍数になるのはもとの数字も3の倍数。
2. 2進数2桁（00,01,10,11）を0個以上足して3の倍数になる最小限のパターンはいくつあるか。
   • 01 01 01
   • 01 01 10 10
   • 01 01 10 01 01
   • 01 10
   • 10 01
   • 10 10 01 01
   • 10 10 10
   • 11
3. 2.の個々のパターンの間に 00 もしくは 11 が0個以上入っても問題ない。
4. 先頭の0が0個以上あるケースとないケース。

以上

以下、これをJavaScriptで検証してみた結果。

var reg = '^(0*(|1(00|11)*01(00|11)*01|1(00|11)*01(00|11)*10(00|11)*10|1(00|11)*01(00|11)*10(00|11)*01(00|11)*01|1(00|11)*10|01(00|11)*01(00|11)*01|01(00|11)*01(00|11)*10(00|11)*10|01(00|11)*01(00|11)*10(00|11)*01(00|11)*01|01(00|11)*10|10(00|11)*01|10(00|11)*10(00|11)*01(00|11)*01|10(00|11)*10(00|11)*10|11))\+$';
for(var i=0;i<100;i++){
  var n = (new Array(10 - i.toString(2).length)).join('0') + i.toString(2);
  if(n.match(reg)){
    console.log(n + ":" + i);
  }
}

// 000000000:0
// 000000011:3
// 000000110:6
// 000001001:9
// 000001100:12
// 000001111:15
// 000010010:18
// 000010101:21
// 000011000:24
// 000011011:27
// 000011110:30
// 000100001:33
// 000100100:36
// 000100111:39
// 000101010:42
// 000101101:45
// 000110000:48
// 000110011:51
// 000110110:54
// 000111001:57
// 000111100:60
// 000111111:63
// 001000010:66
// 001000101:69
// 001001000:72
// 001001011:75
// 001001110:78
// 001010001:81
// 001010100:84
// 001010111:87
// 001011010:90
// 001011101:93
// 001100000:96
// 001100011:99