오일러 프로젝트 65

오일러 프로젝트 65 번 문제는 연분수 표기를 통해 연분수를 전개하고, 그 값을 큰 수로 계산하는 문제이다. 간단치는 않지만 그렇다고 무지막지하게 어려운 난이도는 아니다.

제곱근 2는 아래와 같이 연분수의 꼴로 나타낼 수 있습니다.

연분수에서 이렇게 끝없이 반복되는 부분은 √2 = [1;(2)]처럼 나타낼 수 있는데, 여기서 (2)는 숫자 2가 반복됨을 뜻합니다. 같은 방법으로 √23은 [4;(1,3,1,8)]이 됩니다.

이 연분수의 부분 합을 구하면, 해당 제곱근의 훌륭한 근사값으로 쓸 수 있습니다.. √2의 수렴 과정을 한 번 보겠습니다.

이런 식으로 처음 10번에 해당하는 값은 다음과 같이 됩니다.

정말 놀라운 사실은 가장 중요한 수학 상수 중 하나인 e가 다음과 같은 연분수 꼴로 나타내어진다는 것입니다.

e = [2;1,2,1,1,4,1,1,6,1,…, 1,2k,1…]

이 경우 수렴 과정의 처음 10번은 이렇습니다.

여기서 열 번째 값의 분자 자릿수를 모두 더하면 1+4+5+7 = 17이 되는 것을 알 수 있습니다. 그러면 e의 100번째 연분수 확장 값의 분자 자릿수를 모두 더하면 얼마가 됩니까?

접근

골치가 지끈지끈 아플 것 같은 느낌이지만, 침착하자. 연분수의 모든 마디를 어떻게 구하는지 나와있고, 처음 10개의 연분수 확장 값도 나와있으니 착실히 따라가면 된다. 참고로 여기서는 1, 2, 3, 4…가 아니라 0, 1, 2, 3… 으로 셀 거다. 따라서 문제에서 100번째 연분수 확장값이라 한 것은 99번째 확장값이 된다.

이 문제를 풀기 위해서는 대략 세 가지 정도의 정보가 필요하다.

  1. 연분수를 전개하는데 필요한 임의의 n 번에 해당하는 숫자마디값
  2. 연분수 전개를 위한 규칙. 사실 이건 별거 없고, 재귀적이므로 코드도 짧을 것이다.
  3. 큰 수

연분수 마디 수열

연분수 마디 수열은 다음과 같다.

V : 2; 1, 2, 1, 1, 4, 1, 1, 6, 1,...
n : 0  1  2  3  4  5  6  7  8  9 ...

이 수열의 규칙에서 다음과 같은 것들을 발견할 수 있을 것이다.

  1.  n = 0 일 때에 2이다.
  2. 1, A, 1 의 꼴이 그 이후로 반복된다. 이 때 A 는 짝수로 늘어난다.

점진적으로 변화하는 마디는 3칸이며, 가운데 값은 연속한 짝수이므로 (3칸마다 2배가 된다) 이 수열의 일반항은 다음과 같이 구해진다.

  1. n = 0 : 2
  2. n을 3으로 나눈 나머지가 0, 1 인 경우 : 1
  3. n을 3으로 나눈 나머지가 2 : ((n / 3) + 1 ) * 2

따라서 임의의 n에 대해서 e의 연분수 n 번째 마디를 구하는 함수는 다음과 같이 작성된다.

def m(n):
  if n is 0: return 2
  q, r = divmod(n, 3)
  return (q + 1) * 2 if r is 1 else 1

print([m(x) for x in range(10)])
## [2, 1, 2, 1, 1, 4, 1, 1, 6, 1]

연분수

연분수 전개 방법은 재귀적인데, 그렇다고 재귀함수로 쓸 필요는 없고…. 제곱근을 연분수로 표기하는 것의 역순인데, 분수 계산이라 훨씬 쉽다.

  1. 0번째 값을 구하라고 하면 정수 부분이 된다.
  2. N 번째 값으로 시작하는 경우 N번째 마디값으로 시작한다. (m(n) 사용)
  3. N-1 번째 값과 이전까지의 값의 역수를 더한다.
  4. N이 0이 될 때까지 3의 과정을 반복한다.

파이썬에서는 분수 표현을 위해서 Fraction 클래스를 사용할 수 있다. 이는 기본라이브러리에서 제공되며 fractions 모듈에 포함되어 있다. 따라서 e의 연분수 전개는 다음과 같이 계산할 수 있다.

from fractions import Fraction
def e(n):
  f = fraction(n, 1)
  while n > 0:
    n -= 1
    f = n + (1 / f)
  return f

print([str(e(x)) for x in range(10)])
## ['2', '3', '8/3', '11/4', '19/7', '87/32', '106/39', '193/71', '1264/465', '1457/536']

따라서 Fraction 객체의 분자값은 numerator 라는 속성으로 접근할 수 있다. 따라서 문제의 답은 다음과 같이 간단히 구한다.

print(sum(int(x) for x in str(e(99).numerator)))

Swift 풀이

문제의 답에 해당하는 분자는 58자리나 되는 큰 수이기 때문에, Swift에서는 BigNumber와 같은 큰 수를 위한 별도의 타입을 활용해야 한다. 이전에 작성해둔 이 타입을 이용해서 분수를 표현하는 타입을 작성해보자. BigFraction 이라는 간단한 타입이며, 다음과 같은 기능을 구현해야 한다.

  1. 정수나 BigNumber를 이용해서 인스턴스를 생성하는 이니셜라이저
  2. 역수를 구하는 메소드
  3. 정수와 BigFraction 간의 덧셈

BigFraction

정수, BigNumber로 부터 인스턴스를 생성하거나, 정수/정수, BN/BN의 꼴로 인스턴스를 생성하는 초기화 메소드와, 역수 및 정수와의 덧셈만 구현했다. 참고로 테스트를 위해서 프린트 가능하도록 CustomStringConvertible 을 따르도록 한다.

참고로 이 문제 내의 계산에서는 기약분수 + 정수의 형태만 존재하고 이 때는 분자/분모에 대해 약분이 필요없다.

struct BigFraction: CustomStringConvertible {
  let n : BigNumber /// 분자
  let d : BigNumber /// 분모
  var description: String { return "\(n)/\(d)" }

  init(_ n: BigNumber, _ d: BigNumber) {
    (self.n, self.d) = (n, d)
  }
  init(_ n: BigNumber) {
    (self.n, self.d) = (n, BigNumber(integer: 1))
  }
  init(_ n: Integer) {
    (self.n, self.d) = (BigNumber(integer: n), BigNumber(integer: 1))
  }
  init(_ n: Int, _ d: Int) {
    (self.n, self.d) = (BigNumber(integer: n), BigNumber(integer: d))
  }

  func reversed() -> BigFraction {
    return BigFraction(d, n)
  }

  static func +(left: Int, right: BigFraction) -> BigFraction {
    return BigFraction(left * right.d + right.n, right.d)
  }
}

준비가 끝났으니 다음과 같이 풀이할 수 있다.

func g(_ n: Int) -> Int {
  guard n > 0 else { return 2 }
  return (n % 3 == 2) ? ((n / 3) + 1) * 2 : 1
}

func e(_ n: Int) -> BigFraction {
  var k = n
  var f = BigFraction(g(k))
  while k > 0 {
    k -= 1
    f = g(k) + f.reversed()
  }
  return f
}

print(e(99).n.description.flatMap{ Int(String($0)) }.reduce(0, +))