각 자릿수를 팩토리알 계산해서 합해서 원래의 수가 나오면, 그수를 Digit Factorials 로 정의하기로 합니다. 문제는 이 정의를 만족하는 모든수를 찾은후, 그합을 구하는 문제입니다.
예를 들면, 145 의 경우, 1!+4!+5! = 1+ 24+ 120 = 145 그래서 문제에서 정의한대로 Digit Factorials 가 됩니다. (단, 1,2 는 제외라네요.)
루프만들기(200까지)
def factorial(num):
total=1
while num>1:
total = total * num
num-=1
return total
for i in range(1,200):
total=0
for j in str(i):
total += factorial(int(j))
print(i,total)
1 1 2 2 3 6 4 24 5 120 6 720 7 5040 8 40320 9 362880 10 2 11 2 ...
139 362887 140 26 141 26 142 27 143 31 144 49 145 145 146 745 147 5065 148 40345 149 362905
팩토리알 부분을 함수로 분리하고, 200 까지 루프를 만들면, 145 가 문제에서 설명한 성질을 만족하는것을 볼수 있습니다.
천만까지 테스트
import time
start = time.time()
def factorial(num):
total=1
while num>1:
total = total * num
num-=1
return total
for i in range(1,10000000):
total=0
for j in str(i):
total += factorial(int(j))
if total == i:
print("loop:{} factorial_sum:{} True".format(i,total))
print("Calculation time:",time.time()-start)
loop:1 factorial_sum:1 True loop:2 factorial_sum:2 True loop:145 factorial_sum:145 True loop:40585 factorial_sum:40585 True Calculation time: 125.34990215301514
어디까지 해야할지 알수 없어서, 일단 백천만까지 구해보았습니다. 시간이 꽤 걸리는군요.
최대범위 확인하기.
이런류의 문제는 최대범위를 먼저 설정하면 쉽게 구할수 있습니다.
# 최대 범위 증명
# 7자리 숫자까지 가능.
def factorial(num):
total=1
while num>1:
total = total * num
num-=1
return total
for i in range(1,9):
print("9"*i, factorial(9)*i)
9 362880 99 725760 999 1088640 9999 1451520 99999 1814400 999999 2177280 9999999 2540160 99999999 2903040
위 결과는 각 자릿수의 최대값인 9를 채워놓고, 문제의 정의대로 계산을 했을때의 최대값입니다. 8자리 계산부터는 최대값을 해도 7자리수 밖에 안나오기 때문에, 애초에 문제의 정의를 충족할수가 없습니다. 그래서 7자리까지가 최대범위입니다. 그래서 백만까지 range(1,1000000) 까지만 계산하면 되겠군요.
