오일러 프로젝트 30

오일러 프로젝트 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배 이상 성능이 좋은 듯 ㅠㅠ