Münchausen numbers

Baron Mi1/4nchausen

The number 3435 has the following curious property:

3435 = 3³ + 4⁴ + 3³ + 5⁵.

It is called a Mi1/4nchausen number, an allusion to fictional Baron Mi1/4nchausen. When each digit is raised to its own power and summed, you get the original number back. The only other Mi1/4nchausen number is 1.

At least in base 10. You could look at Mi1/4nchausen numbers in other bases. If you write out a number n in base b, raise each of its "digits" to its own power, take the sum, and get n back, you have a Mi1/4nchausen number in base b. For example 28 is a Mi1/4nchausen number in base 9 because

28_ten = 31_nine = 3³ + 1¹

Daan van Berkel proved that there are only finitely many Mi1/4nchausen in any given base. In fact, he shows that a Mi1/4nchausen number in base b cannot be greater than 2b^b, and so you could do a brute-force search to find all the Mi1/4nchausen numbers in any base.

The upper bound 2b^b grows very quickly with b and so brute force becomes impractical for large b. If you wanted to find all the hexadecimal Mi1/4nchausen numbers you'd have to search 2*16¹⁶ = 36,893,488,147,419,103,232 numbers. How could you do this more efficiently?