連分数

PE 数学

連分数（continued fraction）は、

a_0 + \frac{1}{a_1 + \frac{1}{a_2 + \cdots }}

の形の分数のことを普通は扱うようです。しかし、分子が1でないものも連分数と呼びます。

連分数の略記法

上の連分数は、しばしば

[a0; a1, a2, ...]

と略記されます。

連分数の作り方

例えば、√3を連分数で表してみましょう。まず、これを超えない最大の整数は1です。これを引いてその逆数を取ると、1.366025…。これを超えない最大の整数は1。1を引いて逆数を取ると、2.732051…。これを超えない最大の整数は2。2を引いて逆数を取ると、1.366025…。循環しましたね。正確に計算すると、

1/(√3 - 1) = (√3+1)/2
1/( (√3+1)/2 - 1) = √3+1
1/(√3+1 - 2) = (√3+1)/2
…

このように循環します。よって、

√3 = [1;1,2,1,2,...]

循環しないものも同様にanを求めることができます。

連分数の計算法

pn / qn = [a0; a1, a2, ..., an]

とすると、

p0 = a0
q0 = 1
p1 = a0a1 + 1
q1 = a1

また、

pn = an-1pn-1 + pn-2
qn = an-1qn-1 + qn-2
(n ≥ 2)

これは数学的帰納法で簡単に確認できます。

\frac{p_{n+1}}{q_{n+1}} = \frac{(a_{n-1} + \frac{1}{a_n})p_{n-1} + p_{n-2}}{(a_{n-1} + \frac{1}{a_n})q_{n-1} + q_{n-2}} = \frac{p_n + \frac{p_{n-1}}{a_n}}{q_n + \frac{q_{n-1}}{a_n}}
pn+1 = anpn + pn-1
qn+1 = anqn + qn-1


Project Eulerに必要な用語集
http://d.hatena.ne.jp/inamori/20091225/p1