오일러 프로젝트 57

오일러 프로젝트 57 번 문제는 2의 제곱근을 연분수 형태로 전개하는 것을 단계별로 진행할 때, 각 단계를 기약분수 형태로 만들어서 분자와 분모의 숫자 자리수를 비교하는 문제이다. 일단 자리 수가 엄청나게 커지는 관계로 쉬운 문제는 아니다.

제곱근2는 다음과 같은 연분수의 형태로 나타날 수 있습니다.

\sqrt{2} = 1 + \frac{1}{ 2 + \frac{1}{ 2 + \frac{1}{2 + ... }}} = 1.414213...

위 식을 처음부터 한 단계씩 확장해보면 다음과 같습니다.

1 + 1 / 2 = 3/2 = 1.5
1 + 1 / (2 + 1 / 2) = 7/5 = 1.4
1 + 1 / (2 + 1 / (2 + 1 / 2)) = 17/12 = 1.41666…
1 + 1 / (2 + 1 / (2 + 1 / (2 + 1 / 2))) = 41.29 = 1.41379…

그 다음은 99/70, 239/169, 577/408로 확장이 되다가 여덟번째인 1393/985에 이르면 처음으로 분자의 자리수가 분모의 자릿수를 넘어섭니다. 처음부터 천번째 단계까지 확장하는 중에, 분자의 자리수가 분모의 자리수보다 많아지는 경우는 몇 번이나 됩니까?

접근

분자/분모를 처리할 수 있는 자료 타입과, 연분수를 만들 수 있는 재귀적 자료타입1을 이용해서 연분수를 표현할 수 있다. 문제는 이때의 분자/분모 역시 정수타입의 크기 제약을 받게 된다. (BigNumber 와 같이 큰 수를 지원하는 타입을 사용하려고하면 나머지 연산 등에 대한 부분을 추가해야 한다.)

그런데, 문제의 2의 제곱근의 연분수는 일정한 패턴에 의해서 계산된다. 이 패턴을 잘 살펴보면

  1. n번째 확장한 값 K_n1 + \frac{A_n}{B_n} 을 정리한 값이 된다.
  2. 이때, A1, B1은 각각 1, 2 이다.
  3. 연분수꼴의 확장만 본다면 A_{n+1}, B_{n+1}은 다음과 같이 표현된다.
    \frac{A_{n+1}}{B_{n+1}} = \frac{ 1 }{ 2 + \frac{A_n}{B_n}}
  4. 따라서 다음번 연분수의 분모분자는 1 + \frac{B_n}{2 \cdot B_n + A_n} 이다.

이렇게 각 단계의 분모/분자를 구한 다음, 1 + \frac{A}{B}를 계산한 분모/분자의 자리수를 비교하면 된다.

파이썬 코드

파이썬이야 뭐 어렵지 않지.

def e057():
  a, b, r = 1, 2, 0
  for _ in range(1000):
    # 1 + a/b 값의 분모분자
    x, y = b + a, b
    if len(str(x)) > len(str(y)):
      r += 1
    a, b = b, a + 2 * b
  print(r)
%time e057()
## Wall time: 8 ms

그런데 실제로 이 때 x, y를 찍어보면 380자리가 넘는 큰 수가 나온다.  그렇다면 Swift에서는 큰 수 타입을 써야할까?

Swift 풀이

BigNumber는 4자리 단위로 값을 저장하기 때문에 자리수를 비교해보려면 description을 호출해서 다시 count를 호출하는 식으로 처리해야 한다. 따라서 여기서도 한자리 숫자만 저장하는 배열을 이용해서 더해나가고 (그러면 자리수가 곧 배열의 크기이므로) 비교하자.

func add(_ a:[Int], _ b:[Int]) -> Int {
  var (f, temp) = (0, Array<Int>())
  for i in 0..<(max(a.count, b.count)) {
    let x = (i < a.count) ? a[i] : 0
    let y = (i < b.count) ? b[i] : 0
    var v = x + y + f
    if v > 9 { (f, v) = (v / 10, v % 10) }
    else { f = 0 }
    temp.append(v)
  }
  if f > 0 { temp.append(f) }
  return temp
}

do {
  var (a, b, r) = ([1], [2], 0)
  (1...1000).forEach {
    let (x, y) = (add(a, b), b)
    if x.count > y.count { r += 1 }
    (a, b) = (b, add(b, add(a, b)))
  }
  print(r)
}
## 20.83 ms

 


  1.  https://gist.github.com/sooop/abd63a0c8e5fe36f4e9b5afeeb822c5e