[This (ir)regular expression](http://regex101.com/r/vH3nD8) seems to work.

    ^((?(1)((?(2)\2((?(3)\3((?(4)\4x{24}|x{60}))|x{50}))|x{15}))|x))*$

This basically follows a "difference tree" (not sure if there's a proper name for it), which tells the regex how many more x's to match for the next fourth power:

    1     16    81    256   625   1296  2401 ...
       15    65    175   369   671   1105 ...
          50    110   194   302   434 ...
             60    84    108   132 ...
                24    24    24 ...  # the differences level out to 24 on the 4th iteration

Certainly not an elegant solution, but it does work.