# Number equal to the sum of powers of its digits

I've got another interesting programming/mathematical problem.

For a given natural number q from interval $[2; 10000]$ find the number $n$ which is equal to sum of $q$-th powers of its digits, modulo $2^{64}$.

for example:
for $q=3 \Rightarrow n=153$;
for $q=5 \Rightarrow n=4150$.

This was a programming task which my friend told me quite a long time ago. Now I remembered that and would like to know how such things can be done. How to approach this?

• Why modulo $2^{64}$? – Gerry Myerson Apr 24 '12 at 13:03
• Anyway, see oeis.org/A023052 and the related sequences. – Gerry Myerson Apr 24 '12 at 13:04
• I don't know why $2^{64}$. That was the original problem. I think oeis.org/A003321 is this sequence. But there is very little information. – xan Apr 24 '12 at 13:19
• What information would you like? – Gerry Myerson Apr 25 '12 at 2:12
• I know that I can only dream about closed form formula :-) but I would like something that will help me write a program solves this problem.. – xan Apr 25 '12 at 15:14

You can reduce the number of numbers you have to test.

Say $q=6.$ The maximum sum of $6^{th}$ powers of digits of all $8$-digit numbers is $8\times9^6=4251528$ which has only $7$ digits. So there is no point testing $8$-digit numbers because the sum will never be big enough. The same applies to more than $8$ digits. You can calculate this threshold for each value of $q$.

The threshold for larger values of $q$ will itself be large, which I suppose is where the modulo $2^{64}$ comes in.

Update
Instead of checking all 9-digit numbers, say, to see if they're sums of $9^{th}$ powers, construct all possible $9$-digit sums of $9^{th}$ powers. This is quite quick and and there are surprisingly few of them. Then test this reduced set of candidates to find the solutions you want.

I have written some program code to do this and I find that there are only 32697 candidates to test, instead of the 900 million doing it the long way.

• And that program code is? – Jason Oct 27 '16 at 15:33

Maple code :

q:=3:
for n from 1 to 200 do
s:=n:
r:=0:
while s > 0 do
r:=r+ (s mod 10)^q;
s:=floor(s/10);
end do;
if n = r then
print(n);
end if;
end do;

• why for $n$ from 1 to 200? I thought we don't know anything about $n$, that it can be even larger than $10000$.. – xan Apr 24 '12 at 10:08
• @xan You can set another upper bound for $n$ – Peđa Terzić Apr 24 '12 at 10:10
• Ok, I thought if you set $200$ it means that for $q$ from $[2; 10000]$ it is sufficient. So it is not a sensible solution to this problem. It's a simple brute force. If there is given constraint for $q$ then probably faster algorithm is possible. – xan Apr 24 '12 at 10:45