파이썬으로 수학문제 풀기- 프로젝트 오일러(project euler, 22번부터)

프로젝트 오일러 30번 - 각 자릿수의 5제곱의 합

1634, 8208, 9474 이 세 숫자는 각 자릿수를 4제곱해서 더하면, 원래 그 수가 된다고 합니다. 문제는 각자리를 5제곱해서 원래수가 되는 수들의 합을 찾는 문제입니다.

 

Digit fifth powers

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.

 

일단 Brute Force 방법으로 다 찾아보기로 하죠.

total=0
for i in range(2,1000000):
    string=str(i)
    value=0
    for j in string:
        value+=pow(int(j),5)
    if i == value:
        print(i)
        total+=i
print(total)
4150
4151
54748
92727
93084
194979
443839

백만까지 범위중에는 위처럼 6개 숫자가 존재하고 합은 443839입니다.

 

최대 범위확인

그런데 문제에서 범위를 주지 않았기 때문에, 어디까지 찾아봐야 하느냐가 문제입니다. 그래서 최대값이 존재하는지 알아보도록 하죠. 방법은 각 자릿수 별로, 최대값 9를 모두 채워놓고, 각 자리의 5제곱의 합이 최대 얼마가 생성되는지를 보도록 하겠습니다.

print("1 digit 9",pow(9,5))
print("2 digit 99",pow(9,5)*2)
print("3 digit 999",pow(9,5)*3)
print("4 digit 9999",pow(9,5)*4)
print("5 digit 99999",pow(9,5)*5)
print("6 digit 999999",pow(9,5)*6)
print("7 digit 9999999",pow(9,5)*7)
print("8 digit 99999999",pow(9,5)*8)
1 digit 9 59049
2 digit 99 118098
3 digit 999 177147
4 digit 9999 236196
5 digit 99999 295245
6 digit 999999 354294
7 digit 9999999 413343
8 digit 99999999 472392

9의 5제곱은 59049 입니다. 두자리 99 의 각자릿수 9의 5제곱의 합은 118098 입니다. 한자리수 값의 두배이죠. 이런식으로 계산해나가다가 7자리를 보시면, 7자리숫자의 각자릿수 9의 합은 413343으로 6자리 밖에 안됩니다. 이말은 7자리 숫자는 어떤수를 5제곱해서 더하더라도 최대 6자리 숫자밖에 안나온다는 말이므로, 문제가 요구하는 계산이 불가능하다는 것을 알수있습니다. 그래서 6자리인 백만(전)까지 계산한 결과가 답입니다.

 

댓글

댓글 본문