^                  # N = tail
(?=(x*)\1(x*))     # \1 = floor(N/2); \2 = N%2
((x+(x*))(x?))     # (\3,\4) = x\3\4   = N - A, encoded as a pair to save space;
                   # (\5,\6) = x\5\5\6 = N - B, encoded as a pair (\6 can be shared, as
                   # the parity of A and B will always be the same anyway)
(?=\6*(x?))        # \7 = 1-\6
.*(?=\1$)          # tail = floor(N/2)
(?=
    .*
    (?=\2\7)
    (xx)?          # tail = \2 xor \7 == A%2 == B%2
    ((\7?)x*)      # \9 = tail; \10 = carry for subtraction
)
(?=\9*(x?))        # \11 = 1-\9
# Assert that both A and B are perfect powers
(?!
    \10
    (\4|\5)        # tail = either floor(A/2) or floor(B/2)
    \6
    (?!
        $\11       # for this purpose, accept 1 as a perfect power
    |
        # Assert that tail*2+\9 == M^K where M>=2 and K>=2
        (\11(x*))               # \13 = floor( (potential Kth perfect root of tail*2+\9)     /2);
                                # \13.remainder = \9;
                                # \14 = floor(((potential Kth perfect root of tail*2+\9) - 1)/2);
                                # \14.remainder = \11; tail.remainder = 0
        (?:                               # tail == floor((M^J-M)/2) == floor((M^(J-1)-1)*M/2);
                                          # tail.remainder == 0
            (?=
                (?=
                    \13$\9                # only needed in the case of M==2
                |
                    (?=(\13\13\9)+(x*))   # \15 = \13*2+\9; \16 = remainder
                    (?=.*(?=\15)\16(x*))  # \17 = \15 - \16
                    \17\15*$
                )
                ((x*)(x|(?=(x))))         # \18 = floor(((M^J-M) / (\13*2+\9)  )/2)
                                          # \18.remainder = \21;
                                          # \19 = floor(((M^J-M) / (\13*2+\9)-1)/2)
                                          # \19.remainder = \20;
                                          # tail -= \18; tail.remainder = \21
                (?=
                    \21
                    (
                        (?=\18$)                 # only needed in the case of M==2
                    |
                        (?=(\18\18\21))          # \23 = \18*2+\21
                        (?=
                            \18\18               # do first subtraction without remainder, because
                                                 # tail.remainder - \18.remainder == \21 - \21 == 0
                            \23*
                            (x*)                 # \24 = remainder
                        )
                        (?=.*(?=\23)\24(x*))     # \25 = \23 - \24
                        (?=\25\23*$)
                    )
                )
                (                                # \26 = tool to make tail = \18
                    (?=
                        .*(?=\21$)
                        \11(x*)                  # \27
                    |
                        (x)                      # \28
                    )
                    (?=(\27\28))                 # \29 = \27+\28
                    \21
                    \14\28                       # tail -= \14; tail.remainder = \29
                    (
                        (?=.*(?=\29$)\20$)
                        \19$
                    |
                        (?=
                            (\19\19\20)+         # \31 = \19*2+\20
                            (x*)                 # \32 = remainder
                        )
                        (?=.*(?=\31)\29\32(x*))  # \33 = \31 - \32 - \29
                        \33\31*$
                    )
                )
            )
            (?=.*(?=\21$)\11$)
            \26\14                        # tail = floor((\18*2+\11 + 1 - M)/2); tail.remainder = 0
        )+
        $
    )
)
.*(?=\6\4$)        # tail = N - A; tail.remainder = (N - A).remainder == \7
# Assert that tail*2+\7 == M^K where M==(N-B) and K>=2
(\6(\5))                # \34 = floor((N - B)/2);
                        # \34.remainder = \7;
                        # \35 = \5;
                        # \35.remainder = \6; tail.remainder = 0
(?:                               # tail == floor((M^J-M)/2) == floor((M^(J-1)-1)*M/2);
                                  # tail.remainder == 0
    (?=
        (?=
            \34$\7                # only needed in the case of M==2
        |
            (?=(\34\34\7)+(x*))   # \36 = \34*2+\7; \37 = remainder
            (?=.*(?=\36)\37(x*))  # \38 = \36 - \37
            \38\36*$
        )
        ((x*)(x|(?=(x))))         # \39 = floor(((M^J-M) / (\34*2+\7)  )/2)
                                  # \39.remainder = \42;
                                  # \40 = floor(((M^J-M) / (\34*2+\7)-1)/2)
                                  # \40.remainder = \41;
                                  # tail -= \39; tail.remainder = \42
        (?=
            \42
            (
                (?=\39$)                 # only needed in the case of M==2
            |
                (?=(\39\39\42))          # \44 = \39*2+\42
                (?=
                    \39\39               # do first subtraction without remainder, because
                                         # tail.remainder - \39.remainder == \42 - \42 == 0
                    \44*
                    (x*)                 # \45 = remainder
                )
                (?=.*(?=\44)\45(x*))     # \46 = \44 - \45
                (?=\46\44*$)
            )
        )
        (                                # \47 = tool to make tail = \39
            (?=
                .*(?=\42$)
                \6(x*)                   # \48
            |
                (x)                      # \49
            )
            (?=(\48\49))                 # \50 = \48+\49
            \42
            \35\49                       # tail -= \35; tail.remainder = \50
            (
                (?=.*(?=\50$)\41$)
                \40$
            |
                (?=
                    (\40\40\41)+         # \52 = \40*2+\41
                    (x*)                 # \53 = remainder
                )
                (?=.*(?=\52)\50\53(x*))  # \54 = \52 - \53 - \50
                \54\52*$
            )
        )
    )
    (?=.*(?=\42$)\6$)
    \47\35                        # tail = floor((\39*2+\6 + 1 - M)/2); tail.remainder = 0
)+
$