^ # N = tail = input (?=(x(x*?))(\1\1)+$) # \1 = N / {largest odd divisor of N} # == {largest power of 2 divisor of N}; \2 = \1 - 1 ((x*)(?=\5$))+ # tail = N / {largest power of 2 divisor of N} # == {largest odd divisor of N} (?!(xx+)\6+$) # Assert tail is prime \1\2$ # Assert tail == \1*2 - 1; if this fails to match, it will # backtrack into the "((x*)(?=\5$))+" loop (effectively # multiplying by 2 repeatedly), but this will always fail # to match because every subsequent match attempt will be # an even number, and "\1\2$" can only be odd.