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?

|cite|improve this question
$\endgroup$
  • $\begingroup$ Why modulo $2^{64}$? $\endgroup$ – Gerry Myerson Apr 24 '12 at 13:03
  • $\begingroup$ Anyway, see oeis.org/A023052 and the related sequences. $\endgroup$ – Gerry Myerson Apr 24 '12 at 13:04
  • $\begingroup$ 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. $\endgroup$ – xan Apr 24 '12 at 13:19
  • $\begingroup$ What information would you like? $\endgroup$ – Gerry Myerson Apr 25 '12 at 2:12
  • $\begingroup$ 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.. $\endgroup$ – xan Apr 25 '12 at 15:14
1
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ And that program code is? $\endgroup$ – Jason Oct 27 '16 at 15:33
0
$\begingroup$

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;
|cite|improve this answer
$\endgroup$
  • $\begingroup$ why for $n$ from 1 to 200? I thought we don't know anything about $n$, that it can be even larger than $10000$.. $\endgroup$ – xan Apr 24 '12 at 10:08
  • $\begingroup$ @xan You can set another upper bound for $n$ $\endgroup$ – Peđa Terzić Apr 24 '12 at 10:10
  • $\begingroup$ 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. $\endgroup$ – xan Apr 24 '12 at 10:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.