OFFSET
0,4
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
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).
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
EXAMPLE
The fractions are 1/0, 0/1, 1/1, 2/1, 3/2, 4/3, 7/5, 10/7, 17/12, ...
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 *)
PROG
(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
CROSSREFS
KEYWORD
easy,frac,nonn
AUTHOR
Joshua Zucker, May 08 2006
STATUS
approved