A070879 -id:A070879 - 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).

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

A070878 Stern's diatomic array read by rows (version 2).

Original entry on oeis.org

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

Offset: 0

N. J. A. Sloane, May 20 2002

Row n has length 2^n + 1.

			Triangle begins:
1,0;
1,1,0;
1,2,1,1,0;
1,3,2,3,1,2,1,1,0;
...

Harvey P. Dale, Table of n, a(n) for n = 0..10000
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, A070879, A049455.

Rows sums are A007051. See A293160 for number of distinct terms in each row.

row[1] = {1, 0}; row[n_] := row[n] = (r = row[n-1]; Riffle[r, Most[r + RotateLeft[r]]]); Flatten[ Table[row[n], {n, 1, 7}]] (* Jean-François Alcover, Nov 03 2011 *)
Flatten[NestList[Riffle[#,Total/@Partition[#,2,1]]&,{1,0},6]] (* Harvey P. Dale, Dec 06 2014 *)

Each row is obtained by copying the previous row but interpolating the sums of pairs of adjacent terms. E.g. after 1 2 1 1 0 we get 1 1+2 2 2+1 1 1+1 1 1+0 0.

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

A174980 Stern's diatomic series type ([0,1], 1).

Original entry on oeis.org

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

Peter Luschny, Apr 03 2010

A variant of Stern's diatomic series A002487. See the link [Luschny] and the Maple function below for the classification by types which is based on a generalization of Dijkstra's fusc function.
a(n) is also the number of superduperbinary integer partitions of n.
It appears that a(n) is equal to the multiplicative inverse of A002487(n+2) mod A002487(n+1). - Gary W. Adamson, Dec 23 2023

			The sequence splits into rows of length 2^k:
  0,
  0, 1,
  0, 2, 1, 1,
  0, 3, 2, 3, 1, 2, 1, 1,
  0, 4, 3, 5, 2, 5, 3, 4, 1, 3, 2, 3, 1, 2, 1, 1,
  ...
.
The first few partitions counted are:
[ 0], []
[ 1], []
[ 2], [[2]]
[ 3], []
[ 4], [[4], [2, 2]]
[ 5], [[4, 1]]
[ 6], [[4, 1, 1]]
[ 7], []
[ 8], [[8], [4, 4], [2, 2, 2, 2]]
[ 9], [[8, 1], [4, 4, 1]]
[10], [[8, 2], [8, 1, 1], [4, 4, 1, 1]]
[11], [[8, 2, 1]]
[12], [[8, 2, 2], [8, 2, 1, 1]]
[13], [[8, 2, 2, 1]]
[14], [[8, 2, 2, 1, 1]]
[15], []
[16], [[16], [8, 8], [4, 4, 4, 4], [2, 2, 2, 2, 2, 2, 2, 2]]
[17], [[16, 1], [8, 8, 1], [4, 4, 4, 4, 1]]
[18], [[16, 2], [8, 8, 2], [16, 1, 1], [8, 8, 1, 1], [4, 4, 4, 4, 1, 1]]
[19], [[16, 2, 1], [8, 8, 2, 1]]
[20], [[16, 4], [16, 2, 2], [8, 8, 2, 2], [16, 2, 1, 1], [8, 8, 2, 1, 1]]
[21], [[16, 4, 1], [16, 2, 2, 1], [8, 8, 2, 2, 1]]
[22], [[16, 4, 2], [16, 4, 1, 1], [16, 2, 2, 1, 1], [8, 8, 2, 2, 1, 1]]
[23], [[16, 4, 2, 1]]
[24], [[16, 4, 4], [16, 4, 2, 2], [16, 4, 2, 1, 1]]

Peter Luschny, row(n) for n = 0..12
Edsger Dijkstra, EWD 578: More about the function 'fusc', Selected Writings on Computing, Springer, 1982, p. 232.
Peter Luschny, Rational Trees and Binary Partitions.
Moritz A. Stern, Über eine zahlentheoretische Funktion, J. Reine Angew. Math., 55 (1858), 193-220.

Cf. A002487, A070879, A047679, A007306, A174981, A140429 (row sums), A086449.

SternDijkstra := proc(L, p, n) local k, i, len, M; len := nops(L); M := L; k := n; while k > 0 do M[1+(k mod len)] := add(M[i], i=1..len); k := iquo(k, len); od; op(p, M) end:
a := n -> SternDijkstra([0,1], 1, n);

a[0] = 0; a[n_?OddQ] := a[n] = a[(n-1)/2]; a[n_?EvenQ] := a[n] = a[n/2 - 1] + a[n/2] + Boole[ IntegerQ[ Log[2, n/2]]]; Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Jul 26 2013 *)

# Generating the partitions.
def SDBinaryPartition(n):
    def Double(W, T):
        B = []
        for L in W:
            A = [a*2 for a in L]
            if T > 0: A += [1]*T
            B.append(A)
        return B
    if n == 2: return [[2]]
    if n <  4: return []
    h = n // 2
    H = SDBinaryPartition(h)
    B = Double(H, n % 2)
    if n % 2 == 0:
        H = SDBinaryPartition(h - 1)
        if H != []: B += Double(H, 2)
        if (n & (n - 1)) == 0: B.append([2]*h)
    return B
for n in range(25): print([n], SDBinaryPartition(n)) # Peter Luschny, Sep 02 2019

def A174980(n):
    M = [0, 1]
    for b in n.bits():
        M[b] = M[0] + M[1]
    return M[0]
print([A174980(n) for n in (0..100)]) # Peter Luschny, Nov 28 2017

Recursion: a(2n + 1) = a(n) and a(2n) = a(n - 1) + a(n) + [n = 2^k] for n = 1, a(0) = 0. [n = 2^k] is 1 if n is a power of 2, 0 otherwise.

A174981 Numerators of the L-tree, left-to-right enumeration.

Original entry on oeis.org

0, 1, 1, 2, 3, 1, 2, 3, 5, 2, 5, 3, 4, 1, 3, 4, 7, 3, 8, 5, 7, 2, 7, 5, 8, 3, 7, 4, 5, 1, 4, 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, 6, 11, 5, 14, 9, 13, 4, 15, 11, 18, 7, 17, 10, 13, 3, 14, 11, 19, 8, 21, 13, 18, 5, 17, 12, 19, 7, 16

Offset: 0

Peter Luschny, Apr 03 2010

a(n) is a subsequence of A174980. a(n)/A002487(n+2) enumerates all the reduced nonnegative rational numbers exactly once (L-tree).

			The sequence splits into rows of length 2^k:
0,
1, 1,
2, 3, 1, 2,
3, 5, 2, 5, 3, 4, 1, 3,
4, 7, 3, 8, 5, 7, 2, 7, 5, 8, 3, 7, 4, 5, 1, 4,
...
The fractions are
0/1,
1/2, 1/1,
2/3, 3/2, 1/3, 2/1,
3/4, 5/3, 2/5, 5/2, 3/5, 4/3, 1/4, 3/1,
4/5, 7/4, 3/7, 8/3, 5/8, 7/5, 2/7, 7/2, 5/7, 8/5, 3/8, 7/3, 4/7, 5/4, 1/5, 4/1,
...

Edsger Dijkstra, Selected Writings on Computing, Springer, 1982, p. 232. EWD 578: More about the function fusc.
Peter Luschny, Rational Trees and Binary Partitions.
Moritz A. Stern, Über eine zahlentheoretische Funktion, J. Reine Angew. Math., 55 (1858), 193-220.

Cf. A002487, A070879, A047679, A007306, A174980.

SternDijkstra := proc(L, p, n) local k, i, len, M; len := nops(L); M := L; k := n; while k > 0 do M[1+(k mod len)] := add(M[i], i = 1..len); k := iquo(k, len); od; op(p, M) end:
Ltree := proc(n) 5*2^ilog2(n+1); SternDijkstra([0,1], 1, n + 2 + %) / SternDijkstra([1,0], 2, n + 2) end:
a := proc(n) 5*2^ilog2(n+1); SternDijkstra([0,1], 1, n + 2 + %) end:
seq(a(n), n=0..90);

SternDijkstra[L_, p_, n_] := Module[{k, i, len, M}, len := Length[L]; M = L; k = n; While[k > 0, M[[1 + Mod[k, len]]] = Sum[M[[i]], {i, 1, len}]; k = Quotient[k, len]]; M[[p]]]; Ltree[n_] := With[{k = 5*2^Simplify[ Floor[ Log[2, n + 1]]]}, SternDijkstra[{0, 1}, 1, n + 2 + k]/ SternDijkstra[{1, 0}, 2, n + 2]]; a[0] = 0; a[n_] := With[{k = 5*2^Simplify[ Floor[ Log[2, n + 1]]]}, SternDijkstra[{1, 0}, 1, n + 2 + k]]; row[0] = {a[0]}; row[n_] := Table[a[k], {k, 2^n - 3, 2^(n+1) - 4}] // Reverse; Table[row[n], {n, 0, 6}] // Flatten (* Jean-François Alcover, Jul 26 2013, after Maple *)

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

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

A070878 Stern's diatomic array read by rows (version 2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A174980 Stern's diatomic series type ([0,1], 1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

SageMath

Formula

A174981 Numerators of the L-tree, left-to-right enumeration.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

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