TOPICS
Search

Periodic Continued Fraction

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

A periodic continued fraction is a continued fraction whose terms eventually repeat from some point onwards. The minimal number of repeating terms is called the period of the continued fraction. The properties below concern infinite regular continued fractions. Every such continued fraction, periodic or otherwise, represents a unique irrational number, and each irrational number has a unique infinite regular continued fraction.

The square root of a positive integer n that is not a square number has a periodic continued fraction of the form

sqrt(n)=[a_0;a_1,a_2,a_3,...,a_2,a_1,2a_0^_]
(1)

(Rose 1994, p. 130), where a_0=|_sqrt(n)_| and |_x_| is the floor function. The repeating portion preceding 2a_0 is symmetric upon reversal and may be empty. When it is nonempty, its central term may appear either once or twice.

For such n, the partial denominators of the continued fraction of sqrt(n) satisfy

0<a_k<2sqrt(n)
(2)

for k>=1.

An irrational number has a periodic regular continued fraction iff it is a root of a quadratic polynomial with integer coefficients. A purely periodic tail y of such an expansion satisfies a relation of the form

y=(ay+b)/(cy+d),
(3)

where a, b, c, and d are integers and c>0. This yields a quadratic equation for y and hence for the original irrational number.

PeriodicContinuedFractionPeriods

The periods of the continued fractions of the square roots of the first few nonsquare integers 2, 3, 5, 6, 7, 8, 10, 11, 12, 13, ... (OEIS A000037) are 1, 2, 1, 2, 4, 2, 1, 2, 2, 5, ... (OEIS A013943; Williams 1981, Jacobson et al. 1995). These numbers and their continued fraction representations are summarized in the following table.

Nalpha_(sqrt(N))Nalpha_(sqrt(N))
2[1,2^_]22[4,1,2,4,2,1,8^_]
3[1,1,2^_]23[4,1,3,1,8^_]
5[2,4^_]24[4,1,8^_]
6[2,2,4^_]26[5,10^_]
7[2,1,1,1,4^_]27[5,5,10^_]
8[2,1,4^_]28[5,3,2,3,10^_]
10[3,6^_]29[5,2,1,1,2,10^_]
11[3,3,6^_]30[5,2,10^_]
12[3,2,6^_]31[5,1,1,3,5,3,1,1,10^_]
13[3,1,1,1,1,6^_]32[5,1,1,1,10^_]
14[3,1,2,1,6^_]33[5,1,2,1,10^_]
15[3,1,6^_]34[5,1,4,1,10^_]
17[4,8^_]35[5,1,10^_]
18[4,4,8^_]37[6,12^_]
19[4,2,1,3,1,2,8^_]38[6,6,12^_]
20[4,2,8^_]39[6,4,12^_]
21[4,1,1,2,1,1,8^_]40[6,3,12^_]

An upper bound for the length of the period of sqrt(n) is O(sqrt(n)lnn). The least positive ns such that the continued fraction of sqrt(n) has period p=1, 2, ... are 2, 3, 41, 7, 13, 19, 58, 31, 106, ... (OEIS A013646). The first few values of n such that the continued fraction of sqrt(n) has period p are summarized below for small p.

pOEISn
1A0025222, 5, 10, 17, 26, 37, 50, 65, 82, 101, ...
2A0136423, 6, 8, 11, 12, 15, 18, 20, 24, 27, ...
3A01364341, 130, 269, 370, 458, ...
4A0136447, 14, 23, 28, 32, 33, 34, 47, 55, 60, ...
5A01033713, 29, 53, 74, 85, 89, 125, 173, 185, 218, ...
6A02034719, 21, 22, 45, 52, 54, 57, 59, 70, 77, ...
7A01033858, 73, 202, 250, 274, 314, 349, 425, ...
8A02034831, 44, 69, 71, 91, 92, 108, 135, 153, 158, ...
9A010339106, 113, 137, 149, 265, 389, 493, ...
10A02034943, 67, 86, 93, 115, 116, 118, 129, 154, 159, ...

Assigning period 0 to square numbers, the values of n at which the period of the continued fraction of sqrt(n) reaches a new record are 1, 2, 3, 7, 13, 19, 31, 43, 46, 94, 139, 151, 166, 211, 331, 421, 526, 571, ... (OEIS A013645).

For positive integers a, b, n, a_i, and b_i, and an integer a_0, general identities for periodic continued fractions include

[a^_]=(a+sqrt(a^2+4))/2
(4)
[1,a^_]=(2-a+sqrt(a^2+4))/2
(5)
[a,2a^_]=sqrt(a^2+1)
(6)
[a,b^_]=(ab+sqrt(ab(ab+4)))/(2b)
(7)
[a_1,...,a_n^_]=(-(q_(n-1)-p_n)+sqrt((q_(n-1)-p_n)^2+4q_np_(n-1)))/(2q_n)
(8)
[a_0,b_1,...,b_n^_]=a_0+1/([b_1,...,b_n^_])
(9)
[b_1,...,b_n^_]=([b_1,...,b_n^_]p_n+p_(n-1))/([b_1,...,b_n^_]q_n+q_(n-1))
(10)

(Wall 1948, pp. 39 and 83). In each identity, p_j/q_j is the convergent formed from the first j terms of the displayed repeating block, with p_0=1 and q_0=0.

The first follows from

alpha=a+1/(a+1/(a+1/(a+...)))
(11)
=a+1/(a+(1/(a+1/(a+...)))).
(12)

Therefore,

alpha-a=1/(a+1/(a+1/(a+...))),
(13)

so substituting into the defining expansion gives

alpha=a+1/(a+(alpha-a))=a+1/alpha.
(14)

Expanding

alpha^2-aalpha-1=0,
(15)

and solving using the quadratic formula gives

alpha=(a+sqrt(a^2+4))/2.
(16)

The analog of this treatment in the general case gives

alpha=(alphap_n+p_(n-1))/(alphaq_n+q_(n-1)).
(17)

See also

Continued Fraction, Convergent, Near Noble Number, Noble Number, Quadratic Surd, Simple Continued Fraction

Explore with Wolfram|Alpha

References

Liberman, H. Simple Continued Fractions: An Elementary to Research Level Approach. SMD Stock Analysts, 2003.Rose, H. E. A Course in Number Theory, 2nd ed. Oxford, England: Oxford University Press, 1994.Rosen, K. H. Elementary Number Theory and Its Applications. New York: Addison-Wesley, p. 426, 1980.Sloane, N. J. A. Sequences A000037, A002522, A010337, A010338, A010339, A013642, A013643, A013644, A013645, A013646, A013943, A020347, A020348, and A020349 in "The On-Line Encyclopedia of Integer Sequences."Wall, H. S. Analytic Theory of Continued Fractions. New York: Chelsea, 1948.

Referenced on Wolfram|Alpha

Periodic Continued Fraction

Cite this as:

Weisstein, Eric W. "Periodic Continued Fraction." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/PeriodicContinuedFraction.html

Subject classifications