Take the 2-minute tour ×

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 ?

share|improve this question
I editted the post to try and make the question more clear. If you do not like my edits, feel free to revert back to an earlier version of your post. –  JavaMan Oct 9 '11 at 22:18
It made my post more clear, thanks @DJC :) –  Chris Oct 9 '11 at 22:42
Also see en.wikipedia.org/wiki/Narcissistic_number –  Eric Naslund Oct 21 '11 at 21:00

2 Answers 2

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.

share|improve this answer
Gerry, the sequence you link to requires the number $n$ to have $q$ digits. The OP does not add this criterion. Rather, the sequence I believe is oeis.org/A003321. This sequence makes no restriction on digit length. For example, $4150$ seems to be the smallest number such that $4,150 = 4^5 + 1^5 + 5^5 + 0^5$. However, the smallest $5$ digit number with this property is $54,748$. –  JavaMan Oct 10 '11 at 1:53

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.

share|improve this answer

Your Answer


