正規表現で2のn乗を判定する（Regex Golf をやってみた 18 〜Powers〜）

Regex Golf 18回目（17回目はこちら）は前回に引き続き正規表現で2のn乗を判定する 13問目 "Powers" です。

 

前回は正解を検索する文字列を探してみましたが上手くいきませんでした。
そこで今回は素数の判定でも使った不正解を検索して否定先読みで排除する方針で考えることにします。


素数の判定では素数でなければ1と自身以外の整数で割り切れるという性質を利用しました。

今回は（2の0乗を除外すると）
「2のn乗を素因数分解すると2以外の数値は現れない」
つまり
「2のn乗でない数値は素因数分解すると3以上の奇数が入る」
という性質を利用します。

この条件を満たすには
「3以上の奇数×1以上の数値」
であればよいため

検索対象の先頭から末尾までの文字列が
「x の奇数回(3回以上)繰り返し が 1回以上繰り返す」
であれば2のn乗ではない。という事になります。

x の奇数回(3回以上)繰り返し

x(xx)+

が1回以上繰り返し

(x(xx)+)\1*

が行頭から末尾までと一致しない

^(?!(x(xx)+)\1*$)

でいい気がします。

うん、カンペキですな。
こんな風に見事に解けるとすごく気分がイイですよ。

次回は "Long count" に挑戦です。
難しくて面倒くさくて途方に暮れる問題です。
今から気が重い…

それでは、また。