콘텐츠로 건너뛰기
Home » 오일러 프로젝트 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번째 연분수 확장 값의 분자 자릿수를 모두 더하면 얼마가 됩니까?

접근

문제가 길다보니 괜히 골치가 아픈 것 같은 느낌이지만, 바로 직전 문제에서 자연수의 제곱근을 연분수의 형태로 나타내는 것에 알아보았고, 이번에는 특정 단계까지 이 연분수를 풀어서 가분수의 형태로 만들어 나가는 과정을 계산하면 되는 것이다.

앞 문제에서 연분수 전개를 반복 마디로 표현하는 방법에 대해서 배웠다. 2의 제곱근은 [1; 2] 로 표현한다. 그래서 첫번째 단계는 1 + 1/2 로 3/2 이 된다.

두 번째 단계는 다음과 같이 푼다.

  1. 2 + 1/2 = 5/2 이다.
  2. 1 + (5/2)-1 이므로 1 + 2/5 = 7/5 가 된다.

만약 세 단계까지 진행한다면, 다음과 같이 계산하게 된다.

  1. 2 + 1/2 = 5/2
  2. 2 + 2/5 = 12/5
  3. 1 + 5/12 = 17/12

즉, 반복마디를 계산하고자 하는 단계까지 나열한 뒤에 역수를 취하고 이것을 이전단계의 값과 반복해서 더해나가는 것이다. 참고로 문제에서 첫단계는 1이었으로, 정수 부분만 취하는 것을 1단계로 봐야하고, N단계까지는 반복마디를 N-1 번까지 확장하면 된다.

그러면 문제를 풀기 위해서는 두 가지 도구가 준비되어야 한다.

  1. 반복마디를 만들어 줄 제너레이터
  2. 분수를 계산할 도구.

분수는 파이썬의 fractions.Fraction 타입을 사용하면 간편하다. 분모분자가 얼마든지 커질 수 있고, 자동으로 약분까지 처리해준다.

2의 제곱근의 연분수 전개

우선 문제에서 제시한, 2의 제곱근의 연분수 전개를 구현해보자.

  1. gen() 은 순환마디를 입력받아서 매번 자리의 값을 무한히 만들어주는 제너레이터이다.
  2. take() 는 무한 제너레이터에서 n 번째 값 까지를 얻어주는 제너레이터이다.
  3. foo()는 gen() 과 같이 순환마디를 생성하는 제너레이터와 n을 입력받아서 n 단계만큼 전개한 값을 분수(Fraction)의 형태로 리턴한다.

이 함수들을 사용하여 2의 제곱근의 연분수 전개를 1부터 10까지 구해보고, 검증하자.


from typing import Generator, Iterable, TypeVar
from fractions import Fraction

T = TypeVar("T")

def gen(a: T, bs: Iterable[T]) -> Generator[T, None, None]:
    yield a
    while True:
        for b in bs:
            yield b

def take(xs: Generator[T, None, None], n: int) -> Generator[T, None, None]:
    for _ in range(n):
        yield next(xs)

def foo(g: Generator[int, None, None], n: int) -> Fraction:
    ls = tuple(take(g, n))[::-1]
    res = Fraction(ls[0], 1)
    for x in ls[1:]:
        res = x + 1 / res
    return res

for i in range(10):
    g = foo(gen(1, [2,]), i+1)
    print(g)

자연대수의 연분수 순환마디

자연대수 e 의 연분수꼴 표기는 [2; 1, 2, 1, 1, 4, 1, 1, 6, 1, …] 이며, 자연수의 제곱근과는 달리 순환마디가 생기지 않는다. 이 수열은 3개씩 끊어서 1, 2k, 1 이 무한히 반복된다 (k = 1, 2, 3,…) 앞서 구현한 함수들은 이러한 제너레이터만 있으면 계산이 가능하니까, 제너레이터만 추가로 구현하면 된다. 길이가 100 밖에 안되기 때문에 답은 즉시 나온다.

def eg():
  yield 2
  k = 1
  while True:
    yield 1
    yield k * 2
    yield 1
    k += 1

result = foo(eg(), 100).numerator
print(sum(map(int, str(result)))
태그: