오일러 프로젝트 29

오일러 프로젝트 29 번은 밑과 지수의 조합들에게서 중복을 제외한 값들을 골라내는 작업이다. 일견 단순해 보이는데, 큰 수를 지원하지 않는다면 조금 돌아가야 하는 곤란함이 있다.

 

2 ≤ a ≤ 5 이고 2 ≤ b ≤ 5인 두 정수 a, b로 만들 수 있는 a**b의 모든 조합을 구하면 다음과 같습니다.

2**2=4, 2**3=8, 2**4=16, 2**5=32 3**2=9, 3**3=27, 3**4=81, 3**5=243 4**2=16, 4**3=64, 4**4=256, 4**5=1024 5**2=25, 5**3=125, 5**4=625, 5**5=3125
여기서 중복된 것을 빼고 크기 순으로 나열하면 아래와 같은 15개의 숫자가 됩니다.
4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125
그러면, 2 ≤ a ≤ 100 이고 2 ≤ b ≤ 100인 a, b를 가지고 만들 수 있는 a**b는 중복을 제외하면 모두 몇 개입니까?

http://euler.synap.co.kr/prob_detail.php?id=29

접근

파이썬에서는 2에서 100까지 2단 루프를 돌면서 a^b, ( 2 \le a \le 100, 2 \le b \le 100)의 모든 경우를 계산해서 집합(set())에 담으면 간단하게 계산할 수 있다. 100^100은 엄청 큰 수이지만, 여기서는 별 문제가 되지 않는다.

def e029():
    a = set()
    for x in range(2, 101):
        for y in range(2, 101):
            a.add(x**y)

    print(len(a))

%time e029()
#Wall time: 15 ms

큰수를 지원하지 않는 경우

Swift와 같이 큰수를 지원하지 않는 경우가 문제이다. BigNumber 에 Equtable, Hashable 을 구현해서 파이썬과 똑같이 Set<BigNumber> 를 이용하는 방법도 있겠지만, 여기서는 좀 다른 식으로 접근해보자.  지수로 표현된 값을 튜플로 표현해보자. 예를 들어 8^6의 경우에는 (8, 6) 으로 표시하는 것이다. 그런데 이 값은 사실 (2^3, 6)이고 이는 지수법칙 (a^b)^c = a^{b \times c}에 의해서 (2,18) 과 같아진다.  a의 범위가 2…100 이고 100은 2^7보다 작으므로 2..<a 범위에서 2…7 제곱을 수행하여 매칭되는 케이스가 있으면 변환하면 된다.

참고로 Swift에서 (Int, Int) 타입은 Hashable 이 아니며 따라서 Set에 들어갈 수 없다. 그래서 부득이 하게 “a^b”의 문자열 꼴로 변경해서 저장한다.  최종 구현은 다음과 같다.

import Foundation
func transform(_ x: (Int, Int)) -> (Int, Int) {
  let (a, b) = x
  for i in 2..<a {
    for j in 2..<7 {
      let k = Int(pow(Double(i), Double(j)))
      if k == a { return (i, b * j) }
      if k > a { break }
    }
  }
}

main: do {
  var s = Set<String>()
  for a in 2...100 {
    for b in 2...100 {
      let c = transform(a, b)
      s.insert("\(c.0)^\(c.1)")
    }
  }
  print(s.count)
}