A119016 Numerators of "Farey fraction" approximations to sqrt(2).

1, 0, 1, 2, 3, 4, 7, 10, 17, 24, 41, 58, 99, 140, 239, 338, 577, 816, 1393, 1970, 3363, 4756, 8119, 11482, 19601, 27720, 47321, 66922, 114243, 161564, 275807, 390050, 665857, 941664, 1607521, 2273378, 3880899, 5488420, 9369319, 13250218, 22619537, 31988856

Offset: 0

Author

Joshua Zucker, May 08 2006

Keywords

• easy
• frac
• nonn

Comments

"Add" (meaning here to add the numerators and add the denominators, not to add the fractions) 1/0 to 1/1 to make the fraction bigger: 2/1. Now 2/1 is too big, so add 1/1 to make the fraction smaller: 3/2, 4/3. Now 4/3 is too small, so add 3/2 to make the fraction bigger: 7/5, 10/7, ... Because the continued fraction for sqrt(2) is all 2s, it will always take exactly two terms here to switch from a number that's bigger than sqrt(2) to one that's less. a(n+2) = A082766(n).

a(2n) are the interleaved values of m such that 2*m^2-2 and 2*m^2+2 are squares, respectively; a(2n+1) are the corresponding integer square roots. - Richard R. Forberg, Aug 19 2013

Apart from the first two terms, this is the sequence of numerators of the convergents of the continued fraction expansion sqrt(2) = 1/(1 - 1/(2 + 1/(1 - 1/(2 + 1/(1 - ....))))). - Peter Bala, Feb 02 2017

Examples

			The fractions are 1/0, 0/1, 1/1, 2/1, 3/2, 4/3, 7/5, 10/7, 17/12, ...
		

Links

• G. C. Greubel, Table of n, a(n) for n = 0..1000
• Dave Rusin, Farey fractions on sci.math [Broken link]
• Dave Rusin, Farey fractions on sci.math [Cached copy]
• Index entries for linear recurrences with constant coefficients, signature (0,2,0,1).

Crossrefs

Cf. A097545, A097546 gives the similar sequence for Pi. A119014, A119015 gives the similar sequence for e. A002965 gives the denominators for this sequence. Also very closely related to A001333, A052542 and A000129.

See A082766 for another version.

Programs

Maple

f:= gfun:-rectoproc({a(n+4)=2*a(n+2) +a(n),a(0)=1,a(1)=0,a(2)=1,a(3)=2}, a(n), remember):
map(f, [$0..100]); # Robert Israel, Jun 10 2015

Mathematica

f[x_, n_] := (m = Floor[x]; f0 = {m, m+1/2, m+1}; r = ({a___, b_, c_, d___} /; b < x < c) :> {b, (Numerator[b] + Numerator[c]) / (Denominator[b] + Denominator[c]), c}; Join[{m, m+1}, NestList[# /. r &, f0, n-3][[All, 2]]]); Join[{1, 0 }, f[Sqrt[2], 38]] // Numerator (* Jean-François Alcover, May 18 2011 *)
LinearRecurrence[{0, 2, 0, 1}, {1, 0, 1, 2}, 40] (* and *) t = {1, 2}; Do[AppendTo[t, t[[-2]] + t[[-1]]]; AppendTo[t, t[[-3]] + t[[-1]]], {n, 30}]; t (* Vladimir Joseph Stephan Orlovsky, Feb 13 2012 *)
a0 := LinearRecurrence[{2, 1}, {1, 1}, 20]; (*     A001333 *)
a1 := LinearRecurrence[{2, 1}, {0, 2}, 20]; (* 2 * A000129 *)
Flatten[MapIndexed[{a0[[#]],a1[[#]]} &, Range[20]]] (* Gerry Martens, Jun 09 2015 *)

PARI

x='x+O('x^50); Vec((1 - x^2 + 2*x^3)/(1 - 2*x^2 - x^4)) \\ G. C. Greubel, Oct 20 2017

Formula

From Joerg Arndt, Feb 14 2012: (Start)

a(0) = 1, a(1) = 0, a(2n) = a(2n-1) + a(2n-2), a(2n+1) = a(2n) + a(2n-2).

G.f.: (1 - x^2 + 2*x^3)/(1 - 2*x^2 - x^4). (End)

a(n) = 1/4*(1-(-1)^n)*(-2+sqrt(2))*(1+sqrt(2))*((1-sqrt(2))^(1/2*(n-1))-(1+sqrt(2))^(1/2*(n-1)))+1/4*(1+(-1)^n)*((1-sqrt(2))^(n/2)+(1+sqrt(2))^(n/2)). - Gerry Martens, Nov 04 2012

a(2n) = A001333(n). a(2n+1) = A052542(n) for n>0. - R. J. Mathar, Feb 05 2024