[Project Euler] Problem 30

원문: Problem 30

Surprisingly there are only three numbers that can be written as the sum of fourth powers of their digits:

1634 = 14 + 64 + 34 + 44
8208 = 84 + 24 + 04 + 84
9474 = 94 + 44 + 74 + 44

As 1 = 14 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.

놀랍게도 어떤 수가 그 수의 자리수들의 4제곱의 합으로 표현될 수 있는 수가 오직 3개가 있다:

1634 = 1^4 + 6^4 + 3^4 + 4^4
8208 = 8^4 + 2^4 + 0^4 + 8^4
9474 = 9^4 + 4^4 + 7^4 + 4^4

이 수들의 합은 1634 + 8208 + 9474 = 19316 이다.

어떤 수의 자리수들의 5제곱의 합으로 표현될 수 있는 모든 수들의 합을 찾아라.

일단, 문제에는 수의 최대 제한이 없다. 따라서 먼저 수의 제한을 찾아야 한다.

바로 말하자면, 9^5 + 9^5 + 9^5 + 9^5 + 9^5 + 9^5 = 354294 이다. 즉, 이 수 이상에 대해서는 각 자리수의 5제곱의 합으로 표현하더라도 절대 표현할 수 없다는 것이다. 왜냐하면 6자리 9가 표현할 수 있는 최대값이 354294인데, 이 이상의 수들로 제곱의 합을 표현해봤자 이 수보다는 작을 것이기 때문이다.

또한, 7자리수에서 최대로 나타낼 수 있는 값은 6자리이므로, 7자리 수와는 절대 같아질 수 없다는 것이다.

따라서 확인해야 할 값들은 354294 이하의 수들 뿐이다.

Python

>>> Sum = 0
>>> for k in range(2, 354294):
...     if k == sum(int(i) ** 5 for i in str(k)):
...             Sum += k
... 
>>> print(Sum)

접기