Find smallest number $n\gt 1$ for which the sum of the $q$th power of its digits is $n$

Solution 1:

OEIS does know this sequence; it's http://oeis.org/A014576.

EDIT: As DJC points out in a comment, I was somewhat mistaken. To make amends, I note that these numbers are known under many names: narcissistic numbers, Armstrong numbers, and, my favorite, pluperfect digital invariant numbers. Searching under these terms will turn up many documents. It appears to have been proved that there are exactly 88 such numbers, and that the largest permissible value of $q$ is 39.

Solution 2:

This isn't really an answer just a few observations. So we're interesting in finding the smallest number $a$ such that

$$a=\sum_{i=0}^n a_i 10^i = \sum_{i=0}^n a_i^p,$$

or equivalently

$$\sum_{i=0}^n a_i(10^i-a_i^{p-1})=0.$$ It seems like we could use this formula to do a little bit better than brute force. In particular if we're doing a brute force once we've found $a_0,\dots,a_{n-1}$ we can directly compute $a_n$. There are also a few edge cases you could rule out based on when $(10^i-9^{p-1})>0$. You could also try a variety of approximation methods using the summation formula as your error function.