ContinuedFraction

The regular continued fraction $[a_0; a_1, a_2, \dots]$ of $p/q$. Its partial quotients are the run lengths of the rational's Stern–Brocot path, and the $T$-exponents of its matrix — one object under three names.

✓ checked against that system · ! checked, with disagreements (hover a chip)WikipediaContinued fraction↗MathWorldContinuedFraction↗WikidataQ4115724↗Wolfram LanguageContinuedFraction!↗Rosetta CodeContinued fraction↗

ContinuedFraction(x)the partial quotients of a rational — compute-engine's own head

SageMathlist(continued_fraction(x))SymPylist(continued_fraction(x))

ContinuedFraction(x, n)the first $n$ terms — exact for a quadratic irrational, certified-precision otherwise (compute-engine's own signature, extended)

FromContinuedFraction(list)back to the rational — compute-engine's own

SageMathlist(continued_fraction(list))SymPylist(continued_fraction(list))

FromContinuedFraction([a0, [period]])back to the quadratic irrational, from its periodic-tail shape

SternBrocotPath(p, q)the same data as a word in $L$ and $R$

FareySequence(n)every reduced $p/q$ in $[0,1]$ with $q \le n$, in order

SageMathlist(continued_fraction(n))SymPylist(continued_fraction(n))

Typed signatures

Type	Package	Applies
((list<integer>) -> continued_fraction) & ((real, integer?) -> list<integer>)	number-theoryreplaces modular	always
(real, integer?) -> list<integer>	compute-engine	always
(real, integer?) -> list<integer>	modularreplaces compute-engine	always

Domain: The modular group

Details

• ContinuedFraction and FromContinuedFraction are compute-engine's heads, extended in place rather than redeclared — pass the RATIONAL, not a numerator and denominator, since the two-argument form means "the first $n$ terms"
• For a quadratic irrational $(a+b\sqrt d)/c$, the one-argument form runs the exact PQa algorithm over bigints and returns the eventually-periodic expansion; the two-argument form truncates it. Anything else irrational — $\pi$, $e$, a cube root, a sum of surds, the named GoldenRatio — goes through a BigDecimal extraction certified by agreement across two working precisions, so it isn't limited to double precision
• The expansion is made unique by never ending in $1$: $[\ldots, k, 1]$ is rewritten $[\ldots, k+1]$
• The path is $R^{a_0}L^{a_1}R^{a_2}\cdots$ with the LAST exponent one short — the final step is the arrival, not a turn
• Consecutive Farey fractions satisfy $ps - qr = -1$, which is a determinant, which is a group element
• The Fibonacci fractions alternate $RLRL\dots$, the sense in which $\varphi$ is the most irrational number

Examples

1 more kept as data, checked against the oracles

Basic #

$\pi$'s famous convergent

live ↗

In$\mathrm{ContinuedFraction}(\frac{355}{113})$Out$\bigl\lbrack3, 7, 16\bigr\rbrack$

$5/3 = [1; 1, 2]$

live ↗

In$\mathrm{SternBrocotPath}(5, 3)$Out$\text{RLR}$

$47/17 = 2 + 1/(1 + 1/(3 + 1/4))$

live ↗

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

the first 20 terms of a quadratic irrational — periodic after $a_0$

live ↗

In$\mathrm{ContinuedFraction}(\sqrt{13}, 20)$Out$\bigl\lbrack3, 1, 1, 1, 1, 6, 1, 1, 1, 1, 6, 1, 1, 1, 1, 6, 1, 1, 1, 1\bigr\rbrack$

20 terms of $\pi$, past the 13-term double-precision wall — certified BigDecimal

live ↗

In$\mathrm{ContinuedFraction}(π, 20)$Out$\bigl\lbrack3, 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, 2, 1, 1, 2, 2, 2, 2\bigr\rbrack$

a quadratic irrational's exact expansion is eventually periodic, written with the period as a nested list

live ↗

In$\mathrm{ContinuedFraction}(\sqrt{13})$Out$\bigl\lbrack3, \bigl\lbrack1, 1, 1, 1, 6\bigr\rbrack\bigr\rbrack$

$\sqrt2 = [1; \overline{2}]$

live ↗

In$\mathrm{ContinuedFraction}(\sqrt{2})$Out$\bigl\lbrack1, \bigl\lbrack2\bigr\rbrack\bigr\rbrack$

Scope #

$e$'s pattern $1, 2k, 1$

live ↗

In$\mathrm{ContinuedFraction}(e, 10)$Out$\bigl\lbrack2, 1, 2, 1, 1, 4, 1, 1, 6, 1\bigr\rbrack$

any constant compute-engine can evaluate numerically

live ↗

In$\mathrm{ContinuedFraction}(γ, 10)$Out$\bigl\lbrack0, 1, 1, 2, 1, 2, 1, 4, 3, 13\bigr\rbrack$

a floating-point number, read as the rational it prints as, $649/200$

live ↗

In$\mathrm{ContinuedFraction}(3.245)$Out$\bigl\lbrack3.0, 4.0, 12.0, 4.0\bigr\rbrack$

$\varphi = [1; \overline{1}]$ — purely periodic, so the period is all there is

live ↗

In$\mathrm{ContinuedFraction}(\frac{1+\sqrt{5}}{2})$Out$\bigl\lbrack1, \bigl\lbrack1\bigr\rbrack\bigr\rbrack$

the named constant, unfolded to $(1+\sqrt5)/2$ first

live ↗

In$\mathrm{ContinuedFraction}(\varphi, 10)$Out$\bigl\lbrack1, 1, 1, 1, 1, 1, 1, 1, 1, 1\bigr\rbrack$

a sum of surds — still a quadratic irrational, exact via PQa

live ↗

In$\mathrm{ContinuedFraction}(1+\sqrt{2}, 5)$Out$\bigl\lbrack2, 2, 2, 2, 2\bigr\rbrack$

a cube root, algebraic degree 3 — not periodic, so a certified BigDecimal expansion

live ↗

In$\mathrm{ContinuedFraction}(\sqrt[3]{2}, 10)$Out$\bigl\lbrack1, 3, 1, 5, 1, 1, 4, 1, 1, 8\bigr\rbrack$

symbolic terms build the nested fraction, left uncombined

live ↗

In$\mathrm{FromContinuedFraction}(\bigl\lbrack a, b, c\bigr\rbrack)$Out$a+\frac{1}{b+\frac{1}{c}}$

25 terms, past the 13-term double-precision wall

live ↗

In$\mathrm{ContinuedFraction}(\varphi, 25)$Out$\bigl\lbrack1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1\bigr\rbrack$

A float's continued fraction stops where the digits run out, here after thirteen terms

live ↗

In$\mathrm{ContinuedFraction}(N(π))$Out$\bigl\lbrack3.0, 7.0, 15.0, 1.0, 292.0, 1.0, 1.0, 1.0, 2.0, 1.0, 3.0, 1.0, 14.0\bigr\rbrack$

live ↗

In$\mathrm{ContinuedFraction}(N(π, 20))$Out$\bigl\lbrack3.0, 7.0, 15.0, 1.0, 292.0, 1.0, 1.0, 1.0, 2.0, 1.0, 3.0, 1.0, 14.0\bigr\rbrack$

Applications #

The geometric mean of $\pi$'s partial quotients, near Khinchin's constant $2.685$

live ↗

In$N(\sqrt[1\,000]{\prod\mathrm{ContinuedFraction}(π, 1\,000)})$Out$2.665\,625\,529\,320\,168\,601\,49$

live ↗

In$\mathrm{ContinuedFraction}(\sqrt{e}, 25)$Out$\bigl\lbrack1, 1, 1, 1, 5, 1, 1, 9, 1, 1, 13, 1, 1, 17, 1, 1, 21, 1, 1, 25, 1, 1, 29, 1, 1\bigr\rbrack$

live ↗

In$\mathrm{ContinuedFraction}(e^{\sqrt{163}π}, 10)$Out$\bigl\lbrack262\,537\,412\,640\,768\,743, 1, 1\,333\,462\,407\,511, 1, 8, 1, 1, 5, 1, 4\bigr\rbrack$

Properties #

and back again

live ↗

In$\mathrm{FromSternBrocotPath}(\text{RLR})$Out$\frac{5}{3}$

$1\cdot2 - 3\cdot1 = -1$

live ↗

In$\mathrm{FareyNeighbours}(1, 3, 1, 2)$Out$\mathrm{True}$

FromContinuedFraction inverts it

live ↗

In$\mathrm{FromContinuedFraction}(\mathrm{ContinuedFraction}(\frac{47}{17}))$Out$\frac{47}{17}$

a periodic tail rebuilds the quadratic irrational

live ↗

In$\mathrm{FromContinuedFraction}(\bigl\lbrack3, \bigl\lbrack1, 1, 1, 1, 6\bigr\rbrack\bigr\rbrack)$Out$\sqrt{13}$

$[1; \overline{2}] = \sqrt2$

live ↗

In$\mathrm{FromContinuedFraction}(\bigl\lbrack1, \bigl\lbrack2\bigr\rbrack\bigr\rbrack)$Out$\sqrt{2}$

a plain finite list inverts ContinuedFraction

live ↗

In$\mathrm{FromContinuedFraction}(\bigl\lbrack3, 7, 16\bigr\rbrack)$Out$\frac{355}{113}$

the golden ratio's convergents alternate

live ↗

In$\mathrm{SternBrocotPath}(13, 8)$Out$\text{RLRLR}$

not Farey neighbours

live ↗

In$\mathrm{FareyNeighbours}(1, 3, 2, 3)$Out$\mathrm{False}$

a multi-term pre-period folds too, not just a bare $a_0$

live ↗

In$\mathrm{FromContinuedFraction}(\mathrm{ContinuedFraction}(2-\sqrt{3}))$Out$2-\sqrt{3}$

The first twenty-one terms of $\pi$, the $292$ explaining why $355/113$ is so good

live ↗

In$\mathrm{ContinuedFraction}(π, 21)$Out$\bigl\lbrack3, 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, 2, 1, 1, 2, 2, 2, 2, 1\bigr\rbrack$

Possible issues #

negative: a floor for $a_0$, then positive terms — $-3 + 1/(4 + 1/4)$

live ↗

In$\mathrm{ContinuedFraction}(-\frac{47}{17})$Out$\bigl\lbrack-3, 4, 4\bigr\rbrack$

the two-arg form means $n$ terms of the integer, not a rational

live ↗

In$\mathrm{ContinuedFraction}(355, 113)$Out$\bigl\lbrack355\bigr\rbrack$

Neat examples #

$\coth 1$ has a clean pattern: $[1; 3, 5, 7, 9, \ldots]$, the odd numbers

live ↗

In$\mathrm{ContinuedFraction}(\coth(1), 20)$Out$\bigl\lbrack1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39\bigr\rbrack$

live ↗

In$\mathrm{ContinuedFraction}(\frac{\operatorname{I}_{0}(1)}{\operatorname{I}_{1}(1)}, 20)$Out$\bigl\lbrack2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40\bigr\rbrack$

live ↗

In$\mathrm{ContinuedFraction}(\frac{\operatorname{I}_{1}(2)}{\operatorname{I}_{0}(2)}, 20)$Out$\bigl\lbrack0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19\bigr\rbrack$

About

Examples	37
Checked against	Wolfram Language 28 agree3 differSageMath 6 agree2 differ7 errorSymPy 26 agree2 differ3 error
Crosswalk	WikipediaMathWorldWikidataWolfram LanguageSageMathSymPyRosetta Code

Implementation

mappedwolframpackages/oracle/src/mappings.ts

Sage's continued_fraction returns a ContinuedFraction object (str() is '[3; 7, 16]'); list(...) gives the plain quotients, like the SymPy row.

mappedsympypackages/oracle/src/mappings.ts

Sage's continued_fraction returns a ContinuedFraction object (str() is '[3; 7, 16]'); list(...) gives the plain quotients, like the SymPy row.

mappedsagepackages/oracle/src/mappings.ts

Sage's continued_fraction returns a ContinuedFraction object (str() is '[3; 7, 16]'); list(...) gives the plain quotients, like the SymPy row.

mappedsympypackages/oracle/src/mappings.ts

The first n terms of the expansion, as ours is (an irrational's is not folded into a periodic tail, which the one-argument form does). Exact arguments only: continued_fraction_iterator(3.245) expands the binary double, where ours reads a float as the rational it prints.

See also: ModularWord, IntegerDigits, Convergents