[Python]프로젝트 오일러 #65 : 자연지수 e의 수렴(수학)

프로젝트 오일러 문제 #65는 연분수(continued fraction)와 관련된 문제입니다. 이 문제는 구체적으로 다음과 같습니다.

자연수 \(e\) (오일러의 수)에 대한 연분수 전개는 다음과 같은 형태로 표현됩니다.

e = [2; 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, 1, ...]

여기서 중괄호 안의 숫자들은 연분수 전개의 요소들을 나타냅니다. 연분수의 번째 수렴값은 해당 요소들을 사용하여 얻을 수 있는 분수입니다. 예를 들어, \(e\)의 연분수의 초기 수렴값은 다음과 같습니다:
• 첫 번째 수렴값: \(2\)
• 두 번째 수렴값: \(\frac{3}{1}\)
• 세 번째 수렴값: \(\frac{8}{3}\)

이렇게 계속해서 수렴값이 점점 더 정확하게 \(e\)에 가까워집니다.

문제 요구 사항은 다음과 같습니다:

\(e\)의 연분수 전개의 100번째 수렴값을 계산하고, 이 분수의 분자의 자리수 합을 구하는 것입니다.

continued fraction

 

제가 작성한 소스는 다음과 같습니다.  BigInterger를 사용해야 해서 간단하게 파이썬(Python)을 이용해서 작성했습니다.

"""
    Project Euler #65 - Convergents of e
        - by Aubrey Choi
        - created at 2015-02-19
"""
ub = 100
res = 0

d = 1
n = 2

for i in range(2, ub+1):
    t = d
    c = 1
    if i%3 == 0: c = 2*int(i/3)
    d = n
    n = c * d + t

for c in str(n):
    res = res + int(c)

print(res)

 

 

이 코드는 프로젝트 오일러 문제 #65의 해답으로, e의 연분수 전개에서 100번째 수렴값의 분자의 자리수 합을 계산하는 프로그램입니다. 코드의 주요 흐름과 각 부분을 단계별로 설명하겠습니다.

코드 설명

1. 변수 초기화

ub = 100
res = 0

d = 1
n = 2

• ub: 우리가 구할 의 수렴값의 개수로 설정한 변수입니다. 이 문제에서는 100번째 수렴값을 구하기 때문에 ub = 100으로 설정합니다.
• res: 최종적으로 분자의 자리수를 합산하기 위한 변수입니다.
• d와 n: 각각 현재 수렴값의 분모와 분자를 나타냅니다. 초기값으로 의 첫 번째 수렴값 을 설정합니다.

2. 수렴값 계산 반복문

for i in range(2, ub+1):
    t = d
    c = 1
    if i % 3 == 0: 
        c = 2 * int(i / 3)
    d = n
    n = c * d + t

• for i in range(2, ub+1): 두 번째 수렴값부터 ub 번째 수렴값까지 계산을 반복합니다.
• t = d: 이전 분모 값을 저장합니다.
• c: 현재 항의 계수를 설정하는 변수입니다. 연분수 전개에서 3의 배수 위치에 오는 계수는 으로 설정하고, 나머지 위치에서는 계수를 1로 설정합니다.
• d = n 및 n = c * d + t: 분모와 분자를 업데이트하여 다음 수렴값을 계산합니다.

3. 분자의 자리수 합산

for c in str(n):
    res = res + int(c)

• str(n): 마지막 수렴값의 분자를 문자열로 변환해 각 자리수를 쉽게 접근할 수 있도록 합니다.
• res = res + int(c): 분자의 각 자리수를 res에 누적하여 합산합니다.

4. 결과 출력

print(res)

• 최종적으로 res에 누적된 값, 즉 100번째 수렴값의 분자 자리수 합을 출력합니다.