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

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, 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, 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

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• tabf
• frac
• nice
• look

Comments

Row n has length 2^(n-1) + 1.

A049455/a(n) gives another version of the Stern-Brocot tree.

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.

Largest term of n-th row = A000045(n+1), Fibonacci numbers. - Reinhard Zumkeller, Apr 02 2014

Examples

			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
Array begins
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.5.1
.................................
		

References

• 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.
• W. J. LeVeque, Topics in Number Theory. Addison-Wesley, Reading, MA, 2 vols., 1956, Vol. 1, p. 154.

Links

• Reinhard Zumkeller, Rows n = 1..13 of table, flattened
• C. Giuli and R. Giuli, A primer on Stern's diatomic sequence, Fib. Quart., 17 (1979), 103-108, 246-248 and 318-320 (but beware errors).
• D. H. Lehmer, On Stern's Diatomic Series, Amer. Math. Monthly 36(2) 1929, pp. 59-67.
• D. H. Lehmer, On Stern's Diatomic Series, Amer. Math. Monthly 36(1) 1929, pp. 59-67. [Annotated and corrected scanned copy]
• M. Shrader-Frechette, Modified Farey sequences and continued fractions, Math. Mag., 54 (1981), 60-63.
• N. J. A. Sloane, Stern-Brocot or Farey Tree
• Index entries for sequences related to Stern's sequences

Crossrefs

Coincides with A002487 if pairs of adjacent 1's are replaced by single 1's.

Cf. A049455, A007305, A007306, A006842, A006843, A064881-A064886, A070878, A070879.

Cf. A000051 (row lengths), A034472 (row sums), A293160 (distinct terms in each row).

Programs

Haskell

import Data.List (transpose)
a049456 n k = a049456_tabf !! (n-1) !! (k-1)
a049456_row n = a049456_tabf !! (n-1)
a049456_tabf = iterate
   (\row -> concat $ transpose [row, zipWith (+) row $ tail row]) [1, 1]
-- Reinhard Zumkeller, Apr 02 2014

Maple

A049456 := proc(n,k)
    option remember;
    if n =1 then
        if k >= 0 and k <=1 then
            1;
        else
            0 ;
        end if;
    elif type(k,'even') then
        procname(n-1,k/2) ;
    else
        procname(n-1,(k+1)/2)+procname(n-1,(k-1)/2) ;
    end if;
end proc: # R. J. Mathar, Dec 12 2014

Mathematica

Flatten[NestList[Riffle[#,Total/@Partition[#,2,1]]&,{1,1},10]] (* Harvey P. Dale, Mar 16 2013 *)

Formula

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.

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.