1
$\begingroup$

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?

  • 0
    Maybe you're right. But it is also a mathematical problem. Besides from my experience math.se is much better in algorithmics than stackoverflow.2012-04-26

2 Answers 2

1

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.

  • 0
    And that program code is?2016-10-27
0

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; 
  • 0
    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.2012-04-24