A070878 -id:A070878 - cp's OEIS frontend

A070879 Stern's diatomic array read by rows (version 3 - same as version 2, A070878, but with final 0 in each row omitted).

1, 1, 1, 1, 2, 1, 1, 1, 3, 2, 3, 1, 2, 1, 1, 1, 4, 3, 5, 2, 5, 3, 4, 1, 3, 2, 3, 1, 2, 1, 1, 1, 5, 4, 7, 3, 8, 5, 7, 2, 7, 5, 8, 3, 7, 4, 5, 1, 4, 3, 5, 2, 5, 3, 4, 1, 3, 2, 3, 1, 2, 1, 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, 5, 4, 7, 3, 8

Offset: 0

N. J. A. Sloane, May 20 2002

Row n has length 2^n.
From Yosu Yurramendi, Apr 08 2019: (Start)
The terms (n>0) may be written as a left-justified array with rows of length 2^m:
1,
1, 1,
1, 2, 1, 1,
1, 3, 2, 3, 1, 2, 1, 1,
1, 4, 3, 5, 2, 5, 3, 4, 1, 3, 2, 3, 1, 2, 1, 1,
1, 5, 4, 7, 3, 8, 5, 7, 2, 7, 5, 8, 3, 7, 4, 5, 1, 4, 3, 5, 2, 5, 3, 4,...
as well as right-justified fashion:
                                                                                1,
                                                                             1, 1,
                                                                       1, 2, 1, 1,
                                                           1, 3, 2, 3, 1, 2, 1, 1,
                                   1, 4, 3, 5, 2, 5, 3, 4, 1, 3, 2, 3, 1, 2, 1, 1,
     ... , 2, 7, 5, 8, 3, 7, 4, 5, 1, 4, 3, 5, 2, 5, 3, 4, 1, 3, 2, 3, 1, 2, 1, 1,
...
For properties see FORMULA section.
(End)

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).
Index entries for sequences related to Stern's sequences

Cf. A049456, A070878, A049455.

Rows sums are A007051.

From Yosu Yurramendi, Apr 08 2019: (Start)
a(2^(m+1)+k-1) = A002487(2^m+k); a(2^(m+1)+2^m+k-1) = a(2^m+k-1)  for m >= 0, 0 <= k < 2^m.
a(2^(m+1)-1-(k+1)) = A002487(k+1); a(2^(m+1)+k) - a(2^m+k) = A002487(k)   for m >= 0, 0 <= k < 2^m.
a(2^m-1) = 1 for m >= 0; a(2^(m+1)+k-1) = a(2^(m+1)-k-1) + a(2^m+k-1) for m >= 0, 0 < k < 2^m.
a(2^m+2^m'+k'-1) = a(2^(m'+1)+k'-1)*(m-m'-1) + a(2^m'+k'-1) for m >= 1, 0 <= m' < m, 0 <= k' < 2^m'.
(End)

More terms from Antonio G. Astudillo (afg_astudillo(AT)lycos.com), Apr 07 2003

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

Original entry on oeis.org

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

N. J. A. Sloane

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

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

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.

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

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

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

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

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

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.

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

Original entry on oeis.org

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

N. J. A. Sloane

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

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

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.

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

Cf. A049456. Also A007305, A007306, A006842, A006843, A070878, A070879.
Row sums are A007051.
Cf. A000051 (row lengths), A293165 (distinct terms).

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

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

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

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

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

A293160 Number of distinct terms in row n of Stern's diatomic array, A049456.

Original entry on oeis.org

1, 1, 2, 3, 5, 7, 13, 20, 31, 48, 78, 118, 191, 300, 465, 734, 1175, 1850, 2926, 4597, 7296, 11552, 18278, 28863, 45832, 72356, 114742, 181721, 287926, 455748, 722458, 1144370, 1813975, 2873751, 4553643, 7213620, 11432169, 18120733, 28716294, 45491133

Offset: 0

N. J. A. Sloane, Oct 12 2017, answering a question raised by Barry Carter in an email message. Barry Carter worked out the first 26 terms

Equivalently, a(n) is the number of distinct terms in row n of the Stern-Brocot sequence (A002487) when that sequence is divided into blocks of lengths 1, 2, 4, 8, 16, 32, ...
It would be nice to have a formula or recurrence, or even some bounds. Empirically, a(n) seems to be roughly 2^(2n/3) for the known values. Note that the first half of row n has about 2^(n-2) terms, and the maximal multiplicity is given by A293957(n), so 2^(n-2)/A293957(n) is a lower bound on a(n), which seems not too bad for the known values. - N. J. A. Sloane, Nov 04 2017
The multiset of terms in row n of Stern's diatomic array, with unique elements counted by a(n), is the same as the multiset of numerators of fractions in row n of Kepler's tree. Indeed, a fraction p/q is in row n-1 of Kepler's tree if and only if p/q and q/p are in row n of Calkin-Wilf tree. To form row n of Stern's diatomic array, one should take either numerators and denominators of fractions less than 1 or all numerators from Calkin-Wilf tree row n, in either case p/q and q/p contribute p and q. In Kepler's tree, a fraction p/q contributes p and q as numerators to the next row, i.e. row n. See A294442 for Kepler's tree and A294444 for the number of distinct denominators in it. - Andrey Zabolotskiy, Dec 05 2024

			Row 4 of A294442 contains eight fractions: 1/5, 4/5, 3/7, 4/7, 2/7, 2/7, 3/8, 5/8.
There are five distinct numerators, so a(4) = 5.

R. J. Mathar, Java program to compute the sequence
R. J. Mathar, The Kepler binary tree of reduced fractions
Don Reble, C++ program for A135510 and A293160

Cf. A002487, A049456, A070878, A293161, A293165, A293957.
See A135510 for the smallest positive missing number in each row.
Cf. A294442, A294444, A295783 (first differences).

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
# A293160. This is not especially fast, but it will easily calculate the first 26 terms and confirm Barry Carter's values.
rho:=n->[seq(A049456(n,k),k=0..2^(n-1))];
w:=n->nops(convert(rho(n),set));
[seq(w(n),n=1..26)];
# Alternative program:
# S[n] is the list of fractions, written as pairs [i, j], in row n of Kepler's triangle; nc is the number of distinct numerators, and dc the number of distinct denominators
S[0]:=[[1, 1]]; S[1]:=[[1, 2]];
nc:=[1, 1]; dc:=[1, 1];
for n from 2 to 18 do
S[n]:=[];
for k from 1 to nops(S[n-1]) do
t1:=S[n-1][k];
a:=[t1[1], t1[1]+t1[2]];
b:=[t1[2], t1[1]+t1[2]];
S[n]:=[op(S[n]), a, b];
od:
listn:={};
for k from 1 to nops(S[n]) do listn:={op(listn), S[n][k][1]}; od:
c:=nops(listn);  nc:=[op(nc), c];
listd:={};
for k from 1 to nops(S[n]) do listd:={op(listd), S[n][k][2]}; od:
c:=nops(listd);  dc:=[op(dc), c];
od:
nc; # this sequence
dc; # A294444
# N. J. A. Sloane, Nov 20 2017

Length[Union[#]]& /@ NestList[Riffle[#, Total /@ Partition[#, 2, 1]]&, {1, 1}, 26] (* Jean-François Alcover, Mar 25 2020, after Harvey P. Dale in A049456 *)
Map[Length@ Union@ Numerator@ # &, #] &@ Nest[Append[#, Flatten@ Map[{#1/(#1 + #2), #2/(#1 + #2)} & @@ {Numerator@ #, Denominator@ #} &, Last@ #]] &, {{1/1}, {1/2}}, 21] (* Michael De Vlieger, Apr 18 2018 *)

from itertools import chain, product
from functools import reduce
def A293160(n): return n if n <= 1 else len({1}|set(sum(reduce(lambda x,y:(x[0],x[0]+x[1]) if y else (x[0]+x[1],x[1]),chain(k,(1,)),(1,0))) for k in product((False,True),repeat=n-2))) # Chai Wah Wu, Jun 20 2022

a(28)-a(39) from Don Reble, Oct 16 2017

a(0) prepended and content related to Kepler's tree added from a duplicate entry (where the terms up to a(28) have been independently obtained by Michael De Vlieger) by Andrey Zabolotskiy, Dec 06 2024

A089595 Table T(n,k), n>=0 and k>=0: Stern's diatomic array read by antidiagonals (version 5).

Original entry on oeis.org

1, 0, 1, -1, 1, 1, -3, 0, 2, 1, -2, -1, 1, 3, 1, -7, -1, 1, 2, 4, 1, -5, -4, 0, 3, 3, 5, 1, -8, -3, -1, 1, 5, 4, 6, 1, -3, -5, -1, 2, 2, 7, 5, 7, 1, -13, -2, -2, 1, 5, 3, 9, 6, 8, 1, -10, -9, -1, 1, 3, 8, 4, 11, 7, 9, 1, -17, -7, -5, 0, 4, 5, 11, 5, 13, 8, 10, 1, -7, -12, -4, -1, 1, 7, 7, 14, 6, 15, 9, 11, 1, -18, -5, -7, -1, 3, 2, 10, 9, 17, 7

Offset: 0

Philippe Deléham, Dec 30 2003

			row n=0 : 1, 0, -1, -3, -2, -7, -5, -8, -3, -13, -10, -17, -7, -18, -11, ...
row n=1 : 1, 1, 0, -1, -1, -4, -3, -5, -2, -9, -7, -12, -5, -13, ...
row n=2 : 1, 2, 1, 1, 0, -1, -1, -2, -1, -5, -4, -7, -3, ...
row n=3 : 1, 3, 2, 3, 1, 2, 1, 1, 0, -1, -1, -2, -1, ...
row n=4 : 1, 4, 3, 5, 2, 5, 3, 4, 1, 3, 2, 3, 1, ...

Cf. A049456, A070878, A070879, A049455, A002487.

Each row is obtained by copying the previous row but interpolating the sum of pairs of adjacent terms.
T(n, 2*k) = T(n-1, k) = T(n, k) - A002487(k).
T(n, 2*k+1) = T(n, 2*k) + T(n, 2*k+2); T(0, 0)=1, T(0, 1)=0.
The k-th column is an arithmetic progression with : T(n, k) = T(0, k) + n* A002487(k).

cp's OEIS Frontend

A070879 Stern's diatomic array read by rows (version 3 - same as version 2, A070878, but with final 0 in each row omitted).

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Formula

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Formula

Extensions

A293160 Number of distinct terms in row n of Stern's diatomic array, A049456.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Extensions

A089595 Table T(n,k), n>=0 and k>=0: Stern's diatomic array read by antidiagonals (version 5).

Views

Author

Keywords

Examples

Crossrefs

Formula