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