login
Interleave denominators (A000129) and numerators (A001333) of convergents to sqrt(2).
(Formerly M0671)
28

%I M0671 #147 Aug 01 2024 03:04:35

%S 0,1,1,1,2,3,5,7,12,17,29,41,70,99,169,239,408,577,985,1393,2378,3363,

%T 5741,8119,13860,19601,33461,47321,80782,114243,195025,275807,470832,

%U 665857,1136689,1607521,2744210,3880899,6625109,9369319,15994428,22619537

%N Interleave denominators (A000129) and numerators (A001333) of convergents to sqrt(2).

%C Denominators of Farey fraction approximations to sqrt(2). The fractions are 1/0, 0/1, 1/1, 2/1, 3/2, 4/3, 7/5, 10/7, 17/12, .... See A082766(n+2) or A119016 for the numerators. "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 2's, it will always take exactly two terms here to switch from a number that's bigger than sqrt(2) to one that's less. A097545/A097546 gives the similar sequence for Pi. A119014/A119015 gives the similar sequence for e. - _Joshua Zucker_, May 09 2006

%C The principal and intermediate convergents to 2^(1/2) begin with 1/1, 3/2 4/3, 7/5, 10/7; essentially, numerators=A143607, denominators=A002965. - _Clark Kimberling_, Aug 27 2008

%C (a(2n)*a(2n+1))^2 is a triangular square. - _Hugh Darwen_, Feb 23 2012

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

%C Coefficients of (sqrt(2)+1)^n are a(2n)*sqrt(2)+a(2n+1). - _John Molokach_, Nov 29 2015

%C Apart from the first two terms, this is the sequence of denominators 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

%C Limit_{n->infinity} a(2n+1)/a(2n) = sqrt(2); lim_{n->infinity} a(2n)/a(2n-1) = (2+sqrt(2))/2. - _Ctibor O. Zizka_, Oct 28 2018

%D C. Brezinski, History of Continued Fractions and Padé Approximants. Springer-Verlag, Berlin, 1991, p. 24.

%D Jay Kappraff, Musical Proportions at the Basis of Systems of Architectural Proportion both Ancient and Modern, in Volume I of K. Williams and M.J. Ostwald (eds.), Architecture and Mathematics from Antiquity to the Future, DOI 10.1007/978-3-319-00143-2_27, Springer International Publishing Switzerland 2015. See Eq. 32.7.

%D Serge Lang, Introduction to Diophantine Approximations, Addison-Wesley, New York, 1966.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%D Guelena Strehler, Chess Fractal, April 2016, p. 24.

%H T. D. Noe, <a href="/A002965/b002965.txt">Table of n, a(n) for n = 0..500</a>

%H Damanvir Singh Binner, <a href="https://arxiv.org/abs/2112.15474">Proofs of Chappelon and Alfonsín Conjectures On Square Frobenius Numbers and its Relationship to Simultaneous Pell's Equations</a>, arXiv:2112.15474 [math.NT], 2021.

%H Jonathan Chappelon and Jorge Luis Ramírez Alfonsín, <a href="https://arxiv.org/abs/2006.14219">The Square Frobenius Number</a>, arXiv:2006.14219 [math.NT], 2020.

%H H. S. M. Coxeter, <a href="http://dx.doi.org/10.1016/0021-8693(72)90096-8">The role of intermediate convergents in Tait's explanation for phyllotaxis</a>, J. Algebra 20 (1972), 167-175.

%H Clark Kimberling, <a href="http://dx.doi.org/10.1007/s000170050020">Best lower and upper approximates to irrational numbers</a>, Elemente der Mathematik, 52 (1997) 122-126.

%H Pierre Lamothe, <a href="http://web.archive.org/web/20080624084445/http://www.aei.ca/~plamothe/tangents.htm">En marge du problème des cercles tangents</a>

%H Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.

%H Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992

%H Dave Rusin, <a href="http://www.math.niu.edu/~rusin/known-math/99/farey">Farey fractions on sci.math</a> [Broken link]

%H Dave Rusin, <a href="/A002965/a002965.txt">Farey fractions on sci.math</a> [Cached copy]

%H K. Williams, <a href="http://dx.doi.org/10.1007/BF03024279">The sacred cult revisited: the pavement of the baptistery of San Giovanni, Florence</a>, Math. Intellig., 16 (No. 2, 1994), 18-24.

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

%F a(n) = 2*a(n-2) + a(n-4) if n>3; a(0)=0, a(1)=a(2)=a(3)=1.

%F a(2*n) = a(2*n-1) + a(2*n-2) and a(2*n+1) = 2*a(2*n) - a(2*n-1).

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

%F a(0)=0, a(1)=1, a(n) = a(n-1) + a(2*[(n-2)/2]). - _Franklin T. Adams-Watters_, Jan 31 2006

%F For n > 0, a(2*n) = a(2*n-1) + a(2*n-2) and a(2*n+1) = a(2*n) + a(2*n-2). - _Jon Perry_, Sep 12 2012

%F a(n) = (((sqrt(2) - 2)*(-1)^n + 2 + sqrt(2))*(1 + sqrt(2))^(floor(n/2)) - ((2 + sqrt(2))*(-1)^n -2 + sqrt(2))*(1 - sqrt(2))^(floor(n/2)))/8. - _Ilya Gutkovskiy_, Jul 18 2016

%F a(n) = a(n-1) + a(n-2-(n mod 2)); a(0)=0, a(1)=1. - _Ctibor O. Zizka_, Oct 28 2018

%e The convergents are rational numbers given by the recurrence relation p/q -> (p + 2*q)/(p + q). Starting with 1/1, the next three convergents are (1 + 2*1)/(1 + 1) = 3/2, (3 + 2*2)/(3 + 2) = 7/5, and (7 + 2*5)/(7 + 5) = 17/12. The sequence puts the denominator first, so a(2) through a(9) are 1, 1, 2, 3, 5, 7, 12, 17. - _Michael B. Porter_, Jul 18 2016

%p A002965 := proc(n) option remember; if n <= 0 then 0; elif n <= 3 then 1; else 2*A002965(n-2)+A002965(n-4); fi; end;

%p A002965:=-(1+2*z+z**2+z**3)/(-1+2*z**2+z**4); # conjectured by _Simon Plouffe_ in his 1992 dissertation; gives sequence except for two leading terms

%t LinearRecurrence[{0, 2, 0, 1}, {0, 1, 1, 1}, 42] (* _Vladimir Joseph Stephan Orlovsky_, Feb 13 2012 *)

%t With[{c=Convergents[Sqrt[2],20]},Join[{0,1},Riffle[Denominator[c], Numerator[c]]]] (* _Harvey P. Dale_, Oct 03 2012 *)

%o (PARI) a(n)=if(n<4,n>0,2*a(n-2)+a(n-4))

%o (PARI) x='x+O('x^100); concat(0, Vec((x+x^2-x^3)/(1-2*x^2-x^4))) \\ _Altug Alkan_, Dec 04 2015

%o (JavaScript)

%o a=new Array(); a[0]=0; a[1]=1;

%o for (i=2;i<50;i+=2) {a[i]=a[i-1]+a[i-2];a[i+1]=a[i]+a[i-2];}

%o document.write(a); // _Jon Perry_, Sep 12 2012

%o (Haskell)

%o import Data.List (transpose)

%o a002965 n = a002965_list !! n

%o a002965_list = concat $ transpose [a000129_list, a001333_list]

%o -- _Reinhard Zumkeller_, Jan 01 2014

%o (Magma) I:=[0,1,1,1]; [n le 4 select I[n] else 2*Self(n-2)+Self(n-4): n in [1..50]]; // _Vincenzo Librandi_, Nov 30 2015

%o (GAP) a:=[0,1];; for n in [3..45] do a[n]:=a[n-1]+a[n-2-((n-1) mod 2)]; od; a; # _Muniru A Asiru_, Oct 28 2018

%Y Cf. A000129(n) = a(2n), A001333(n) = a(2n+1).

%Y Cf. A001109, A155046.

%K nonn,easy,nice,frac

%O 0,5

%A _N. J. A. Sloane_

%E Thanks to _Michael Somos_ for several comments which improved this entry.