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

프로젝트 오일러 34번 문제 - Digit Factorials

각 자릿수를 팩토리알 계산해서 합해서 원래의 수가 나오면, 그수를 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) 까지만 계산하면 되겠군요.

댓글

댓글 본문
작성자
비밀번호
graphittie 자세히 보기