Convergents

The successive convergents $p_k/q_k$ of a continued fraction, given as its list of terms or as the number itself.

✓ checked against that system · ! checked, with disagreements (hover a chip)Wolfram LanguageConvergents✓↗

Convergents(list)the convergents of a term list, such as one ContinuedFraction returns

Convergents(x)every convergent of a rational $x$ — the last one is $x$ itself

Convergents(x, n)the first $n$ convergents of $x$, via ContinuedFraction(x, n)

Typed signatures

Type	Package	Applies
(value, integer?) -> list<number>	modular	always

Domain: The modular group

Details

• The two-term recurrence $p_k = a_k p_{k-1} + p_{k-2}$, $q_k = a_k q_{k-1} + q_{k-2}$, seeded $p_{-1}=1, p_{-2}=0, q_{-1}=0, q_{-2}=1$ — the same recurrence ModularMatrix multiplication runs, one $T^{a_k}S$ at a time
• Every convergent is in lowest terms, and each is a better rational approximation of $x$ than any fraction with a smaller denominator
• Convergents(x) (no n) needs a RATIONAL $x$, since ContinuedFraction(x) alone does; an irrational needs Convergents(x, n)

Examples

Basic #

from a list of terms

live ↗

In$\mathrm{Convergents}(\bigl\lbrack3, 7, 15, 1\bigr\rbrack)$Out$\bigl\lbrack3, \frac{22}{7}, \frac{333}{106}, \frac{355}{113}\bigr\rbrack$

the first five convergents of $\pi$

live ↗

In$\mathrm{Convergents}(π, 5)$Out$\bigl\lbrack3, \frac{22}{7}, \frac{333}{106}, \frac{355}{113}, \frac{103\,993}{33\,102}\bigr\rbrack$

Ratios of consecutive Fibonacci numbers, since every quotient is $1$

live ↗

In$\mathrm{Convergents}(\varphi, 10)$Out$\bigl\lbrack1, 2, \frac{3}{2}, \frac{5}{3}, \frac{8}{5}, \frac{13}{8}, \frac{21}{13}, \frac{34}{21}, \frac{55}{34}, \frac{89}{55}\bigr\rbrack$

Convergents from a list of quotients directly

live ↗

In$\mathrm{Convergents}(\bigl\lbrack1, 1, 1, 1, 1\bigr\rbrack)$Out$\bigl\lbrack1, 2, \frac{3}{2}, \frac{5}{3}, \frac{8}{5}\bigr\rbrack$

Scope #

a rational: the last convergent is the number itself

live ↗

In$\mathrm{Convergents}(\frac{47}{17})$Out$\bigl\lbrack2, 3, \frac{11}{4}, \frac{47}{17}\bigr\rbrack$

The classic approximations of $\pi$: $22/7$, $355/113$, $103993/33102$

live ↗

In$\mathrm{Convergents}(π, 10)$Out$\bigl\lbrack3, \frac{22}{7}, \frac{333}{106}, \frac{355}{113}, \frac{103\,993}{33\,102}, \frac{104\,348}{33\,215}, \frac{208\,341}{66\,317}, \frac{312\,689}{99\,532}, \frac{833\,719}{265\,381}, \frac{1\,146\,408}{364\,913}\bigr\rbrack$

Convergents to $\sqrt7 = [2; 1,1,1,4,1,1,1,4,\ldots]$

live ↗

In$\mathrm{Convergents}(\sqrt{7}, 10)$Out$\bigl\lbrack2, 3, \frac{5}{2}, \frac{8}{3}, \frac{37}{14}, \frac{45}{17}, \frac{82}{31}, \frac{127}{48}, \frac{590}{223}, \frac{717}{271}\bigr\rbrack$

A rational's convergents end exactly at the number itself

live ↗

In$\mathrm{Convergents}(\frac{7}{17})$Out$\bigl\lbrack0, \frac{1}{2}, \frac{2}{5}, \frac{7}{17}\bigr\rbrack$

Applications #

convergents of $\sqrt2$ solve Pell's equations $p^2 - 2q^2 = \pm1$

live ↗

In$\mathrm{Convergents}(\sqrt{2}, 5)$Out$\bigl\lbrack1, \frac{3}{2}, \frac{7}{5}, \frac{17}{12}, \frac{41}{29}\bigr\rbrack$

Properties #

Errors against $\pi$ alternate in sign and shrink rapidly

live ↗

In$\mathrm{Convergents}(π, 10)-N(π)$Out$\bigl\lbrack-0.141\,592\,653\,589\,793\,238\,462\,643, 0.001\,264\,489\,267\,349\,618\,677\,357, -0.000\,083\,219\,627\,529\,087\,522\,643, 0.000\,000\,266\,764\,189\,062\,417\,357, -5.778\,906\,343\,926\,43\cdot10^{-10}, 3.316\,278\,062\,473\,57\cdot10^{-10}, -1.223\,565\,329\,426\,43\cdot10^{-10}, 2.914\,338\,493\,735\,7\cdot10^{-11}, -8.715\,467\,262\,643\cdot10^{-12}, 1.610\,740\,017\,357\cdot10^{-12}\bigr\rbrack$

About

Examples	10
Checked against	Wolfram Language 10 agree
Crosswalk	Wolfram Language

See also: ContinuedFraction, ContinuedFractionK