Problem Description

Surprisingly there are only three numbers that can be written as the sum of fourth powers of their digits:
1634 = 1⁴ + 6⁴ + 3⁴ + 4⁴
8208 = 8⁴ + 2⁴ + 0⁴ + 8⁴
9474 = 9⁴ + 4⁴ + 7⁴ + 4⁴

As 1 = 1⁴ is not a sum it is not included.

The sum of these numbers is 1634 + 8208 + 9474 = 19316.

Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.

Analysis

Firstly, “Find the sum” means we will need to build a solution set of valid elements that meet the problem’s criteria, and then add them together to verify we have calculated the correct and complete set.

Secondly, we make a list of constraints which place limits or restriction on the solution set. This problem excludes the candidate 1 from consideration. In fact, by intuitive extension, it is excluding all single digit candidates (numbers < 10) as they cannot form a sum of digits. This is a clue that our search range starts from at least 10. The truly ambitious may discover a method to calculate the optimal range minimum.

Finally, we write a brute-force program to see if it can derive the correct answer within the one minute time limit. The only concern is how much search range to consider. We have already determined the range minimum to be 10 so it’s finding the range maximum that remains a challenge. After just a moment of thought it becomes clear that the number of digits for the sum must have the same number of digits as a candidate, so we construct the table below:

In fact, it turns out that 9⁵ x (n-1) is actually more than adequate, which reduces the search range and improves the performance of the program. This was proved empirically.

Solution

We try our solution not only for the target exponent of 5 (about 3 seconds) but also for 3, 4, 6, and 7. This confirms that the program also works for cases of other powers and is keeping with our aim of extensibility.

$exp = 5; $t = 0;
 
for $n ( 10 .. 9**$exp * ($exp-1) ) {
  $s = 0;
  $s+= $_**$exp for split //,$n; #split the digits in $n and assign each to $_.
  if ($s==$n) {$t+=$s; print "$n  "}
}
print "n total: $t for exp = $expn";

Comments

A Google search of the given series in the problem description found:
“Fixed points for operation of repeatedly replacing a number by the sum of the fourth power of its digits.” (series A052455)
With a little further searching, we found:
“Fixed points for operation of repeatedly replacing a number by the sum of the fifth power of its digits.” (series A052464)
We also discovered a series of numbers that are related to this set called narcissistic numbers (or Armstrong numbers) which differ from our target solution set by restricting the number of digits to be equal to the exponent (series A005188).

Runs with other exponents
153 370 371 407
total: 1301 for exp = 3

1634 8208 9474
total: 19316 for exp = 4

548834
total: 548834 for exp = 6

1741725 4210818 9800817 9926315 14459929
total: 40139604 for exp = 7

Comparative Languages

Mathematica: Sum[Boole[n == Tr[IntegerDigits[n]^5]] n, {n, 2, 1*^6}]
When calculating the answer for exp=7 the Perl program took 7 minutes, 16 seconds on a modest PC. In contrast, the C++ version, listed below, took only 43 seconds; that’s about 10 times faster.
We used our C++ program to calculate exp=8 which took about 10 minutes as compared to hours in Perl.

C++ Source: 565 sec. execution time

#include "stdafx.h"
#include "math.h"
 
int main() { 
 
int i,s,t=0,exp=8;
long long  max = pow(9.0,exp) * (exp-1);
for (int n = 10; n < max; n++) {
  s=0;
  i=n;
  while (i > 0) { 
    s += pow((double)(i%10),exp); 
    i /= 10; 
  }
  if ( s == n) {printf("%11u, ", n);t+=s;} 
}
printf("n total: %11u for exp = %2d", t,exp);
}

Output:
24678050, 24678051, 88593477
total: 137949578 for exp = 8