오일러 프로젝트 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번째 확장값이 된다.
이 문제를 풀기 위해서는 대략 세 가지 정도의 정보가 필요하다.
- 연분수를 전개하는데 필요한 임의의 n 번에 해당하는 숫자마디값
- 연분수 전개를 위한 규칙. 사실 이건 별거 없고, 재귀적이므로 코드도 짧을 것이다.
- 큰 수
연분수 마디 수열
연분수 마디 수열은 다음과 같다.
V : 2; 1, 2, 1, 1, 4, 1, 1, 6, 1,... n : 0 1 2 3 4 5 6 7 8 9 ...
이 수열의 규칙에서 다음과 같은 것들을 발견할 수 있을 것이다.
- n = 0 일 때에 2이다.
- 1, A, 1 의 꼴이 그 이후로 반복된다. 이 때 A 는 짝수로 늘어난다.
점진적으로 변화하는 마디는 3칸이며, 가운데 값은 연속한 짝수이므로 (3칸마다 2배가 된다) 이 수열의 일반항은 다음과 같이 구해진다.
- n = 0 : 2
- n을 3으로 나눈 나머지가 0, 1 인 경우 : 1
- 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]연분수
연분수 전개 방법은 재귀적인데, 그렇다고 재귀함수로 쓸 필요는 없고…. 제곱근을 연분수로 표기하는 것의 역순인데, 분수 계산이라 훨씬 쉽다.
- 0번째 값을 구하라고 하면 정수 부분이 된다.
- N 번째 값으로 시작하는 경우 N번째 마디값으로 시작한다. (
m(n)사용) - N-1 번째 값과 이전까지의 값의 역수를 더한다.
- 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 이라는 간단한 타입이며, 다음과 같은 기능을 구현해야 한다.
- 정수나 BigNumber를 이용해서 인스턴스를 생성하는 이니셜라이저
- 역수를 구하는 메소드
- 정수와 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, +))