# The following comments assume that the input is a perfect power.
^                    # N^K = tail, where N>=2 and K>=2
(x(x+))              # \1 = N; \2 = N-1
(
    (?=
        (?=\1+$)
        (x(x*))      # \4 = tail / N; \5 = \4-1
        (?=\4+$)
        (\2\5+$)     # \6 = tool to make tail = \4
    )
    \6\2             # tail = \4+1 - N
)+
$