오일러 프로젝트 30 번은 각 자리 수를 n 제곱하여 더했을 때 자기 자신이 되는 수를 찾는 문제이다.
각 자리의 숫자를 4제곱해서 더했을 때 자기 자신이 되는 수는 놀랍게도 단 세 개밖에 없습니다. 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 (1 = 1**4의 경우는 엄밀히 말해 합이 아니므로 제외합니다) 위의 세 숫자를 모두 더하면 1634 + 8208 + 9474 = 19316 입니다. 그렇다면, 각 자리 숫자를 5제곱해서 더했을 때 자기 자신이 되는 수들의 합은 얼마입니까?
http://euler.synap.co.kr/prob_detail.php?id=30
접근
9의 5제곱은 59049이다. 따라서 6자리까지는 답이 있을 가능성이 있지만 0~9까지의 5제곱값을 더해서 7자리 수를 만드려면 7개 이상의 숫자가 필요하기 때문에 답은 999,999 이하의 범위에 있다. 그렇다하더라도 이 루프는 약 100만번을 돌아야하고, 파이썬으로 검사했을 때, 이는 거의 10초 가까이 (물론 요즘 PC로는 이 정도까지는 안나오겠지만…) 시간이 걸려야 한다. 일단 코드는 다음과 같이 매우 단순하다.
def transform(num, n):
return sum((int(x) ** n for x in str(num)))
def e030():
result = sum((x for x in range(2, 999999+1) if x == transform(x, 5)))
print(result)
%time e030()
# Wall time: 7.08 s최적화
9의 5제곱이 59049이므로 6자리 숫자중 가장 큰 999,999를 변환한 값은 354,294이다. 이렇게만해도 검사해야 하는 구간이 절반 이하로 떨어진다. 일단은 이정도에 만족…
보너스: Swift 풀이
실행결과 : http://swift.sandbox.bluemix.net/#/repl/599fb27fffaee1404783d414
import Foundation
// 파이썬은 문자열로 바꿔서 변환하는게 유리한데 비해서
// Swift는 문자열 <-> 정수 변환이 의외로 오래 걸림
func translate(_ n: Int) -> Int {
let c = Int(log10(Double(n))) // 자리수를 체크
let xs = (0...c).map{ n / Int(pow(10, Double($0))) % 10 }
.map{ Int(pow(Double($0), 5))) }
return xs.reduce(0, +)
}
main: do {
print((1...354294).filter{ translate($0) == $0 }.reduce(0. +))
}사족 : 이 코드의 Bluemix 웹 컴파일러 수행속도가 1.6초대인데, 대략 내 mac보다 2배 이상 성능이 좋은 듯 ㅠㅠ