Project Euler 30: Find the sum of all the numbers that can be written as the sum of fifth powers of their digits

Project Euler 30 Problem Description

Project Euler 30: 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.

Project Euler 30 Analysis

These numbers are somewhat related to Armstrong numbers (or narcissistic numbers) which differ from having more or fewer digits than the exponent to only allowing the same number of digits as the exponent (series Reference: The On-Line Encyclopedia of Integer Sequences (OEIS) A005188: Armstrong (or Plus Perfect, or narcissistic) numbers: n-digit numbers equal to sum of n-th powers of their digits (a finite sequence, the last term being 115132219018763992565095597973971522401).).

The easiest and fastest way to solve this problem is to use brute force searching which solves this and the HackerRank version within the time limit. All we need is the maximum number of digits to search through for the chosen exponent which happens to safely be the exponent+1. This saves having to argue what the upper limit should be and serially checking every number in a range.

Using combinations

In the problem statement above, 1634 was used as the first example that satisfies the summation of powers requirement. It becomes obvious that various combinations of 1634 (1643, 1346, 1364, 1436, 1463, 3146, 3164, 3416, 3461, 3614, 3641, 4136, 4163, 4316, 4361, 4613, 4631, 6134, 6143, 6314, 6341, 6413, 6431) will all evaluate to the same sum. Clearly, we can eliminate all but one combination and just test that candidate from the set.

This reduces our search space from tens of thousands numbers to only a couple thousand. Since all the numbers evaluate to the same power-sum by virtue of the commutative law of addition, it doesn’t matter which number from the set we choose, as long as its power-sum, subjected to the same process, is equal to the sum’s digits and unique in the search.

Example: Take arbitrarily from the set above, say 3614, and sum the 4th powers of its digits. The sum is 1634 as it is for any number in the set. Now, let’s do the same calculation on the sum, 1634: 1⁴+6⁴+3⁴+4⁴ = 1634. When the two sums are equal, 1634 is the successful candidate from the set.

HackerRank only goes as far as extending the problem to 6th powers of their digits when 11 or 12 digits would be more challenging and quickly solved using this method.

This program and method
solves all test cases for
Project Euler 30 on HackerRank

Comments

• 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.

• Power	Number Set
  2	*NONE*
  3	153, 370, 371, 407
  4	1634, 8208, 9474
  5	4150, 4151, 54748, 92727, 93084, 194979
  6	548834
  7	1741725, 4210818, 9800817, 9926315, 14459929
  8	24678050, 24678051, 88593477
  9	146511208, 472335975, 534494836, 912985153
  10	4679307774
  11	32164049650, 40028394225, 42678290603, 44708635679, 49388550606, 32164049651, 82693916578, 94204591914
  12	*NONE*
  13	564240140138
  14	28116440335967
  15	*NONE*
  16	4338281769391370, 4338281769391371
  17	233411150132317, 21897142587612075, 35641594208964132, 35875699062250035
  18	*NONE*
  19	1517841543307505039, 3289582984443187032, 4498128791164624869, 4929273885928088826
  20	63105425988599693916