Continued fractions

The first n terms in the continued fraction representation for a number x can be found from the built-in Mathematica function ContinuedFraction, or from

Floor[NestList[1/Mod[#, 1]&, x, n - 1]]

A rational approximation to the number x can be reconstructed from the continued fraction using FromContinuedFraction or by

Fold[(1/#1 + #2 )&, Last[list], Rest[Reverse[list]]]

The pictures below show the digit sequences of successive iterates obtained from NestList[1/Mod[#, 1]&, x, n] for several numbers x.

Unlike ordinary digits, the individual terms in a continued fraction can be of any size. In the continued fraction for a randomly chosen number, the probability to find a term of size s is Log[2, (1 + 1/s)/(1 + 1/(s + 1))], so that the probability of getting a 1 is about 41.50%, and the probability of getting a large term falls off like 1/s^{2}. If one looks at many terms, then their geometric mean is finite, and approaches Khinchin's constant Khinchin ≃ 2.68545.

In the first 1000 terms of the continued fraction for π, there are 412 1's, and the geometric mean is about 2.6656. The largest individual term is the 432th one, which is equal to 20,776. In the first million terms, there are 414,526 1's, the geometric mean is 2.68447, and the largest term is the 453,294th one, which is 12,996,958.

Note that although the usual continued fraction for π looks quite random, modified forms such as

4/(Fold[(#2/#1 + 2)&, 2, Reverse[Range[1, n, 2]^{2}]] - 1)

can be very regular.

The continued fractions for Exp[2/k] and Tan[1/2k] have simple forms (as discussed by Leonhard Euler in the mid-1700s); other rational powers of E and tangents do not appear to. The sequence of odd numbers gives the continued fraction for Coth[1]; the sequence of even numbers for BesselI[0, 1]/BesselI[1, 1]. In general, continued fractions whose n^{th} term is a n + b correspond to numbers given by BesselI[b/a, 2/a]/BesselI[b/a + 1, 2/a]. Numbers whose continued fraction terms are polynomials in n can presumably also be represented in terms of suitably generalized hypergeometric functions. (All so-called Hurwitz numbers have continued fractions that consist of interleaved polynomial sequences—a property left unchanged by x (a x + b)/(c x + d).)

As discovered by Jeffrey Shallit in 1979, numbers of the form Sum[1/k^{2}^{i}, {i, 0, ∞}] that have nonzero digits in base k only at positions 2^{i} turn out to have continued fractions with terms of limited size, and with a nested structure that can be found using a substitution system according to

{0, k - 1, k + 2, k, k, k - 2, k, k + 2, k - 2, k}〚Nest[Flatten[{{1, 2}, {3, 4}, {5, 6}, {7, 8}, {5, 6}, {3, 4}, {9, 10}, {7, 8}, {9, 10}, {3, 4}}〚#〛]&, 1, n]〛

The continued fractions for square roots are always periodic; for higher roots they never appear to show any significant regularities. The first million terms in the continued fraction for 2^{1/3} contain 414,983 1's, have geometric mean 2.68505, and have largest term 4,156,269 at position 484,709. Terms of any size presumably in the end always occur in continued fractions for higher roots, though this is not known for certain. Fairly large terms are sometimes seen quite early: in 5^{1/3} term 19 is 3052, while in Root[10 + 8 # - #^{3}&, 1] term 34 is 1,501,790. The presence of a large term indicates a close approximation to a rational number. In a few known cases simple formulas yield numbers that are close but not equal to integers. An example discovered by Srinivasa Ramanujan around 1913 is Exp[π √163], which is an integer to one part in 10^{30}, and has second continued fraction term 1,333,462,407,511. (This particular example can be understood from the fact that as d increases Exp[π √d] becomes extremely close to -1728 KleinInvariantJ[(1 + √-d)/2], which turns out to be an integer whenever there is unique factorization of numbers of the form a + b √-d—and d = 163 is the largest of the 9 cases for which this is so.) Other less spectacular examples include Exp[π]-π and 163/Log[163].

Numbers with digits given by concatenation sequences in any base k (see note above) seem to have unusual continued fractions, in which most terms are fairly small, but some are extremely large. Thus with k = 2, term 30 is 4,534,532, term 64 is 4,682,854,730,443,938, term 152 is about 2*10^{34} and term 669,468 is about 2*10^{78902}. (For the k = 10 case of the original Champernowne number, even term 18 is already about 5*10^{165.}) The plots below of the numbers of digits in successive terms turn out to have patterns of peaks that show some signs of nesting.

In analogy to digits in a concatenation sequence the terms in the sequence

Flatten[Table[Rest[ContinuedFraction[a/b]], {b, 2, n}, {a, b - 1}]]

are known to occur with the same frequencies as they would in the continued fraction representation for a randomly chosen number.

The pictures below show as a function of n the quantity

With[{r = FromContinuedFraction[ContinuedFraction[x, n]]}, -Log[Denominator[r], Abs[x - r]]]

which gives a measure of the closeness of successive rational approximations to x. For any irrational number this quantity cannot be less than 2, while for algebraic irrationals Klaus Roth showed in 1955 that it can only have finitely many peaks that reach above any specified level.