A331101 Denominators of the best approximations for sqrt(2).

1, 2, 3, 5, 12, 17, 29, 70, 99, 169, 408, 577, 985, 2378, 3363, 5741, 13860, 19601, 33461, 80782, 114243, 195025, 470832, 665857, 1136689, 2744210, 3880899, 6625109, 15994428, 22619537, 38613965, 93222358, 131836323, 225058681, 543339720, 768398401, 1311738121, 3166815962

Offset: 1

Author

Gerhard Kirchner, Jan 09 2020

Keywords

• nonn
• frac
• easy

Comments

For numerators, see A331115.

Let w = sqrt(2). Each of the principal convergents 1/1, 3/2, 7/5, 17/12, ..., see A002965, represents a best approximation for w because no other fraction with a smaller denominator is closer to w.

However, with abs(3/2 - w) > abs(4/3 - w)> abs(7/5 - w), 4/3 is another best approximation which has to be inserted. Generally, after each principal convergent p/q, we must insert the correspondent intermediate convergent 2q/p = (2/1), 4/3, (10/7), 24/17, ..., if it is closer to w than p/q (terms without brackets).

It is a well-known fact that the geometric mean sqrt(a*b) of two factors a and b is closer to the smaller one. As w is the geometric mean of p/q and 2q/p, the second term is inserted if it is smaller than p/q. This applies to every second intermediate convergent because the principal convergents alternately undershoot and overshoot w.

Examples

			The fractions are 1/1, 3/2, 4/3, 7/5, 17/12, 24/17, ...
Let w = sqrt(2) again. The first four principal convergents are, see comments, 1/1 (which is less than w), 3/2 (greater than w), 7/5 (less than w), 17/12 (greater than w). After 3/2, the fraction 2 * 2/3 = 4/3 is inserted because 4/3 < 3/2 and therefore w - 4/3 < 3/2 - w (0.081... < 0.085...). After 7/5, the fraction 2 * 5/7 = 10/7 is not inserted, because 10/7 > 7/5 etc.
		

Links

• Gerhard Kirchner, Table of n, a(n) for n = 1..200
• Index entries for linear recurrences with constant coefficients, signature (0,0,6,0,0,-1).

Crossrefs

Cf. A002965, A331115, A001333, A143607, A000129.

Programs

PARI

Vec(x*(1 + 2*x + 3*x^2 - x^3 - x^5) / (1 - 6*x^3 + x^6) + O(x^40)) \\ Colin Barker, Jan 09 2020

Formula

If n mod 3 = 2: a(n) = 3*a(n - 1) - a(n - 2), otherwise: a(n) = a(n - 1) + a(n - 2), with a(1) = 1, a(2) = 2.

a(3n - 2) = w/4*D(2n - 1), a(3n - 1) = w/4*D(2n), a(3n) = 1/2*S(2n), for n>0 with w = sqrt(2) and S(n) = (1 + w)^n + (1 - w)^n and D(n) = (1 + w)^n - (1 - w)^n.

From Colin Barker, Jan 09 2020: (Start)

G.f.: x*(1 + 2*x + 3*x^2 - x^3 - x^5) / (1 - 6*x^3 + x^6).

a(n) = 6*a(n - 3) - a(n - 6) for n > 6.

(End)