Project Euler Problem 30 Statement

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.

Solution

These numbers differ from Armstrong numbers (or narcissistic numbers) by allowing more or fewer digits than the exponent.

Brute-force, simple search solution

The easiest and fastest way to solve this problem is to use brute force which solves this and the HackerRank version within the time limit.

print(sum(i for i in range(2, 5*9**5) if i==sum(int(j)**5 for j in str(i))))

We only need to check up to a certain limit because, beyond a certain point, numbers become too large to be written as the sum of their digit powers. This is calculated as: n*9**n, n=5

Using Combinations

In the problem statement, 1634 is presented as the first example of a number that satisfies the requirement of being equal to the sum of the fourth powers of its digits. It becomes clear that different permutations of 1634 (such as 1643, 1346, 1364, and 20 others) will all yield the same sum when their digits are raised to the fourth power. We can use this knowledge to only have one representative from this group instead of 23 thereby eliminating redundancy.

For instance, 1634 or 6431 will NOT be in the set created by combinations_with_replacement. Only the lowest variant 1346 will. But, when we check pow_digits(1346)=1634 and it equals pow_digits(pow_digits(1346))=1634 then 1634 is a hit.

Program Explanation

1. pow_digits(): First, we need a helper function that computes the sum of each digit in a number raised to the n-th power. We use a pre-calculated list, q[], for the powers to increase efficency.
2. Check Each Number in the Range: For each combination, t, we calculate the sum of its digits raised to the n-th power using pow_digits(). If this sum equals t itself, then t is a number we are looking for.
3. Sum the Numbers Found: The final result is the sum of all numbers that meet this criterion. We subtract 1 from the sum to remove the 1ⁿ case as instructed.

HackerRank version

Solves all test cases for Hackerrank Project Euler Problem 30

HackerRank Project Euler 30 varies the exponent to 3, 4, 5, or 6.

Last Word

• Reference: The On-Line Encyclopedia of Integer Sequences (OEIS) A052455: Fixed points for operation of repeatedly replacing a number by the sum of the fourth power of its digits.
• With a little further searching, I found:
  Reference: The On-Line Encyclopedia of Integer Sequences (OEIS) A052464: Fixed points for operation of repeatedly replacing a number by the sum of the fifth power of its digits.