cp's OEIS Frontend

A049456 Triangle T(n,k) = denominator of fraction in k-th term of n-th row of variant of Farey series. This is also Stern's diatomic array read by rows (version 1).

%I A049456 #33 Jan 05 2025 19:51:35
%S A049456 1,1,1,2,1,1,3,2,3,1,1,4,3,5,2,5,3,4,1,1,5,4,7,3,8,5,7,2,7,5,8,3,7,4,
%T A049456 5,1,1,6,5,9,4,11,7,10,3,11,8,13,5,12,7,9,2,9,7,12,5,13,8,11,3,10,7,
%U A049456 11,4,9,5,6,1,1,7,6,11,5,14,9,13,4,15,11,18,7,17,10,13,3,14,11,19,8,21,13
%N A049456 Triangle T(n,k) = denominator of fraction in k-th term of n-th row of variant of Farey series. This is also Stern's diatomic array read by rows (version 1).
%C A049456 Row n has length 2^(n-1) + 1.
%C A049456 A049455/a(n) gives another version of the Stern-Brocot tree.
%C A049456 Define mediant of a/b and c/d to be (a+c)/(b+d). We get A006842/A006843 if we omit terms from n-th row in which denominator exceeds n.
%C A049456 Largest term of n-th row = A000045(n+1), Fibonacci numbers. - _Reinhard Zumkeller_, Apr 02 2014
%D A049456 J. C. Lagarias, Number Theory and Dynamical Systems, pp. 35-72 of S. A. Burr, ed., The Unreasonable Effectiveness of Number Theory, Proc. Sympos. Appl. Math., 46 (1992). Amer. Math. Soc.
%D A049456 W. J. LeVeque, Topics in Number Theory. Addison-Wesley, Reading, MA, 2 vols., 1956, Vol. 1, p. 154.
%H A049456 Reinhard Zumkeller, <a href="/A049456/b049456.txt">Rows n = 1..13 of table, flattened</a>
%H A049456 C. Giuli and R. Giuli, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Scanned/17-2/giuli.pdf">A primer on Stern's diatomic sequence</a>, Fib. Quart., 17 (1979), 103-108, 246-248 and 318-320 (but beware errors).
%H A049456 D. H. Lehmer, <a href="http://dx.doi.org/10.2307/2299356">On Stern's Diatomic Series</a>, Amer. Math. Monthly 36(2) 1929, pp. 59-67.
%H A049456 D. H. Lehmer, <a href="/A002487/a002487_1.pdf">On Stern's Diatomic Series</a>, Amer. Math. Monthly 36(1) 1929, pp. 59-67. [Annotated and corrected scanned copy]
%H A049456 M. Shrader-Frechette, <a href="http://www.jstor.org/stable/2690435">Modified Farey sequences and continued fractions</a>, Math. Mag., 54 (1981), 60-63.
%H A049456 N. J. A. Sloane, <a href="/stern_brocot.html">Stern-Brocot or Farey Tree</a>
%H A049456 <a href="/index/St#Stern">Index entries for sequences related to Stern's sequences</a>
%F A049456 Each row is obtained by copying the previous row but interpolating the sums of pairs of adjacent terms. E.g. after 1 2 1 we get 1 1+2 2 2+1 1.
%F A049456 Row 1 of Farey tree is 0/1, 1/1. Obtain row n from row n-1 by inserting mediants between each pair of terms.
%e A049456 0/1, 1/1; 0/1, 1/2, 1/1; 0/1, 1/3, 1/2, 2/3, 1/1; 0/1, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 1/1; 0/1, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, ... = A049455/A049456
%e A049456 Array begins
%e A049456 1...............................1
%e A049456 1...............2...............1
%e A049456 1.......3.......2.......3.......1
%e A049456 1...4...3...5...2...5...3...4...1
%e A049456 1.5.4.7.3.8.5.7.2.7.5.8.3.7.4.5.1
%e A049456 .................................
%p A049456 A049456 := proc(n,k)
%p A049456     option remember;
%p A049456     if n =1 then
%p A049456         if k >= 0 and k <=1 then
%p A049456             1;
%p A049456         else
%p A049456             0 ;
%p A049456         end if;
%p A049456     elif type(k,'even') then
%p A049456         procname(n-1,k/2) ;
%p A049456     else
%p A049456         procname(n-1,(k+1)/2)+procname(n-1,(k-1)/2) ;
%p A049456     end if;
%p A049456 end proc: # _R. J. Mathar_, Dec 12 2014
%t A049456 Flatten[NestList[Riffle[#,Total/@Partition[#,2,1]]&,{1,1},10]] (* _Harvey P. Dale_, Mar 16 2013 *)
%o A049456 (Haskell)
%o A049456 import Data.List (transpose)
%o A049456 a049456 n k = a049456_tabf !! (n-1) !! (k-1)
%o A049456 a049456_row n = a049456_tabf !! (n-1)
%o A049456 a049456_tabf = iterate
%o A049456    (\row -> concat $ transpose [row, zipWith (+) row $ tail row]) [1, 1]
%o A049456 -- _Reinhard Zumkeller_, Apr 02 2014
%Y A049456 Coincides with A002487 if pairs of adjacent 1's are replaced by single 1's.
%Y A049456 Cf. A049455, A007305, A007306, A006842, A006843, A064881-A064886, A070878, A070879.
%Y A049456 Cf. A000051 (row lengths), A034472 (row sums), A293160 (distinct terms in each row).
%K A049456 nonn,easy,tabf,frac,nice,look
%O A049456 1,4
%A A049456 _N. J. A. Sloane_