프로젝트 오일러 034
각 자리 수의 팩토리얼의 합이 원래의 수와 같은 신기한 수
접근
앞의 30번 문제와 여러 모로 비슷한 점이 많은 문제입니다. 30번 문제에서 그렇게 했던 것처럼, 각 자리 수의 팩토리얼의 합계를 내는 연산을 편의상, ‘오렌지 따기’라고 마음대로 이름붙이겠습니다.
오렌지따기 연산은 그 수가 원래의 값보다 급격하게 늘어나는 것처럼 보입니다. Orange(25) = 2! + 5! = 2 + 120 = 122 이고, Orange(78) = 7! + 8! = 45360입니다. 한 자리 수 중에서 팩토리얼이 가장 큰 수는 9이고 그 팩토리얼은 362,880입니다. 99에서 999로 증가할 때 원래의 수는 900만큼 증가하지만 오렌지 따기 연산의 결과는 362,880만큼 증가합니다. 오렌지 따기 연산이 훨씬 크게 증가하는 것 같지만, 이 연산의 결과는 자리 수가 늘어나도라도 동일한 크기로만 증가합니다. 99,999 -> 999,999는 900,000만큼 증가하는데 오렌지 따기의 결과는 여전히 362,880만큼만 증가합니다. 따라서 어느 시점 이후부터는 오렌지따기의 결과가 원래의 수보다 적어지는 시점이 온다는 것입니다.
9!은 6자리수입니다. 7자리 수인 9,999,999의 오렌지따기 결과는 2,549,160으로 여전히 7자리 수입니다. 즉, 2,549,160보다 큰 수는 오렌지 따기를 했을 때 자신보다 작아진다는 것을 의미합니다. 그러나 2,549,160이 오렌지따기의 최대치가 될까요? 더 낮출 수 있는지 살펴봅시다. 이 값보다 작으면서 9가 가장 많이 나올 수 있는 수는 2,499,999입니다. 이 수의 오렌지 따기는 1,814,416입니다. 역시 원래 수보다 작습니다. 그러면 이 수보다 작으면서 9가 많은 1,799,999는 어떨가요? 오렌지 따기 결과는 1,819,441입니다. 원래의 수보다 오렌지따기가 더 커지므로, 오렌지따기 한계점은 1,184,416이라고 봐야 할 것 같습니다.
그러면 1부터 1,184,416사이 범위의 모든 수에 대해서 오렌지따기를 계산하고 그 값이 원래의 수와 같은 것을 찾으면 됩니다.
fs = [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880]
def orange(n):
return sum(fs[int(c)] for c in str(n))
def main():
sum(x for x in range(1, 1819441) if orange(x) == x)
if __name__ == '__main__':
main()팩토리얼 수
각 자리 숫자의 팩토리얼 값의 합이 원래의 수와 같은 수를 ‘팩토리얼 수’라고 합니다. 팩토리얼 수는 십진수 체계에서 단 4개 밖에 존재하지 않아 아주 특별한 수로 취급되는 경향이 있습니다. 온라인 정수 배열 사전인 OEIS에도 등재되어 있습니다.