A049455 Triangle read by rows: T(n,k) = numerator of fraction in k-th term of n-th row of variant of Farey series.

0, 1, 0, 1, 1, 0, 1, 1, 2, 1, 0, 1, 1, 2, 1, 3, 2, 3, 1, 0, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, 1, 0, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, 1, 5, 4, 7, 3, 8, 5, 7, 2, 7, 5, 8, 3, 7, 4, 5, 1, 0, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, 1, 5, 4, 7, 3, 8, 5, 7, 2, 7, 5, 8, 3, 7, 4, 5, 1, 6, 5, 9

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• tabf
• frac
• look

Comments

Stern's diatomic array read by rows (version 4, the 0,1 version).

This sequence divided by A049456 gives another version of the Stern-Brocot tree.

Row n has length 2^n + 1.

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), 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
The 0,1 version of Stern's diatomic array (cf. A002487) begins:
0,1,
0,1,1,
0,1,1,2,1,
0,1,1,2,1,3,2,3,1,
0,1,1,2,1,3,2,3,1,4,3,5,2,5,3,4,1,
0,1,1,2,1,3,2,3,1,4,3,5,2,5,3,4,1,5,4,7,3,8,5,7,2,7,5,3,3,7,4,5,1,
...
		

References

• Martin Gardner, Colossal Book of Mathematics, Classic Puzzles, Paradoxes, and Problems, Chapter 25, Aleph-Null and Aleph-One, p. 328, W. W. Norton & Company, NY, 2001.
• 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

• Robert G. Wilson v, Table of n, a(n) for n = 1..10000 (first 8204 terms from Reinhard Zumkeller)
• 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).
• Jennifer Lansing, Largest Values for the Stern Sequence, J. Integer Seqs., 17 (2014), #14.7.5.
• 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

Cf. A049456. Also A007305, A007306, A006842, A006843, A070878, A070879.

Row sums are A007051.

Cf. A000051 (row lengths), A293165 (distinct terms).

Programs

Haskell

import Data.List (transpose)
import Data.Ratio ((%), numerator, denominator)
a049455 n k = a049455_tabf !! (n-1) !! (k-1)
a049455_row n = a049455_tabf !! (n-1)
a049455_tabf = map (map numerator) $ iterate
   (\row -> concat $ transpose [row, zipWith (+/+) row $ tail row]) [0, 1]
   where u +/+ v = (numerator u + numerator v) %
                   (denominator u + denominator v)
-- Reinhard Zumkeller, Apr 02 2014

Mathematica

f[l_List] := Block[{k = Length@l, j = l}, While[k > 1, j = Insert[j, j[[k]] + j[[k - 1]], k]; k--]; j]; NestList[f, {0, 1}, 6] // Flatten (* Robert G. Wilson v, Nov 10 2019 *)

PARI

mediant(x, y) = (numerator(x)+numerator(y))/(denominator(x)+denominator(y));
newrow(rowa) = {my(rowb = []); for (i=1, #rowa-1, rowb = concat(rowb, rowa[i]); rowb = concat(rowb, mediant(rowa[i], rowa[i+1]));); concat(rowb, rowa[#rowa]);}
rows(nn) = {my(rowa); for (n=1, nn, if (n==1, rowa = [0, 1], rowa = newrow(rowa)); print(apply(x->numerator(x), rowa)););} \\ Michel Marcus, Apr 03 2019

Formula

Row 1 is 0/1, 1/1. Obtain row n from row n-1 by inserting mediants between each pair of terms.

Extensions

More terms from Larry Reeves (larryr(AT)acm.org), Apr 12 2000