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
    Why modulo $2^{64}$?2012-04-24
  • 0
    Anyway, see http://oeis.org/A023052 and the related sequences.2012-04-24
  • 0
    I don't know why $2^{64}$. That was the original problem. I think http://oeis.org/A003321 is this sequence. But there is very little information.2012-04-24
  • 0
    What information would you like?2012-04-25
  • 0
    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..2012-04-25
  • 0
    If it's a question about writing a program, maybe you should take it to a programming site.2012-04-25
  • 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
    why for $n$ from 1 to 200? I thought we don't know anything about $n$, that it can be even larger than $10000$..2012-04-24
  • 0
    @xan You can set another upper bound for $n$2012-04-24
  • 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