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

Question

Today I came across this problem:

For a given integer $q$, find the smallest natural number $n > 1$ such that sum of the $q$th powers of its digits is equal to $n$.

For example, we can't find any number for $q=2$, but we can do it for $q=3$, and it's $153$ because $153$ is the smallest number such that $$1^3+5^3+3^3 = 153.$$ For $q=4$, the smallest such $n$ is $1634$.

I tried to find any properties by writing very simple brute force to check every possible number. Moreover, OEIS doesn't know this sequence.

Is there any better and more interesting approach ?

Answer 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.

Answer 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.