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

%I #34 Jan 14 2020 07:53:27

%S 1,2,3,5,12,17,29,70,99,169,408,577,985,2378,3363,5741,13860,19601,

%T 33461,80782,114243,195025,470832,665857,1136689,2744210,3880899,

%U 6625109,15994428,22619537,38613965,93222358,131836323,225058681,543339720,768398401,1311738121,3166815962

%N Denominators of the best approximations for sqrt(2).

%C For numerators, see A331115.

%C 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.

%C 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).

%C 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.

%H Gerhard Kirchner, <a href="/A331101/b331101.txt">Table of n, a(n) for n = 1..200</a>

%H <a href="/index/Rec#order_06">Index entries for linear recurrences with constant coefficients</a>, signature (0,0,6,0,0,-1).

%F 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.

%F 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.

%F From _Colin Barker_, Jan 09 2020: (Start)

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

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

%F (End)

%e The fractions are 1/1, 3/2, 4/3, 7/5, 17/12, 24/17, ...

%e 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.

%o (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

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

%K nonn,frac,easy

%O 1,2

%A _Gerhard Kirchner_, Jan 09 2020