Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
show 2 more comments

2 Answers

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;
share|improve this answer
    
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$ –  pedja 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
    
@xan maybe..... –  pedja Apr 24 '12 at 10:54
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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