A049456 -id:A049456 - cp's OEIS frontend

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

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

A135510 Least positive number missing from row n of Stern's diatomic array (see A049456 or A002487).

Original entry on oeis.org

2, 3, 4, 6, 6, 14, 20, 28, 38, 54, 90, 150, 216, 350, 506, 876, 1230, 2034, 3160, 4470, 7764, 12190, 18816, 29952, 43800, 73968, 112602, 182210, 285780, 474558, 729432, 1194078, 1843110, 2990880, 4662450, 7608720, 11801580, 18489120, 29790300

Offset: 1

mc (da-da(AT)lycos.de), Feb 09 2008

nonn

The old definition was "Least numbers not generated by Eisenstein's algorithm: m=1 n=1, then insert between them m+n, at stage p=1. (E.g. next stage (p=2) of Eisenstein's algorithm would be m, m+m+n, m+n, m+n+n, n). The maximum of these symmetric row elements at stage p is fibonacci(p+2); but how to determine the first number not generated at stage p?"

Don Reble, C++ program for A135510 and A293160
G. Eisenstein, Über ein einfaches Mittel zur Auffindung der höheren Reciprocitätsgesetze und der mit ihnen zu verbindenden Ergänzungssätze, Journal für die reine und angewandte Mathematik, Volume 39 (1850), page 351ff.
M. A. Stern, Über eine zahlentheoretische Funktion, J. Reine Angew. Math., 55 (1858), 193-220.

Cf. A049456, A002487, A293160.

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
mex := proc(L)
        local k;
        for k from 1 do
                if not k in L then
                        return k;
                end if;
        end do:
end proc:
rho:=n->[seq(A049456(n,k),k=0..2^(n-1))];
[seq(mex(rho(n)),n=1..16)]; # N. J. A. Sloane, Oct 14 2017

(* T is A049456 *)
T[n_, k_] := T[n, k] = If[n == 1, If[k >= 0 && k <= 1, 1, 0], If[EvenQ[k], T[n-1, k/2], T[n-1, (k+1)/2] + T[n-1, (k-1)/2]]];
mex[L_] := Module[{k}, For[k = 1, True, k++, If[FreeQ[L, k], Return[k]]]];
rho[n_] := Table[T[n, k], {k, 0, 2^(n-1)}];
a[n_] := a[n] = mex[rho[n]];
Table[Print[n, " ", a[n]]; a[n], {n, 1, 25}] (* Jean-François Alcover, Aug 03 2023, after Maple code *)

Entry revised by N. J. A. Sloane, Oct 14 2017

a(29)-a(39) from Don Reble, Oct 16 2016

A178031 Consider the Farey tree A049455/A049456; a(n) = row at which the denominator n first appears (assumes first row is labeled row 1).

Original entry on oeis.org

1, 2, 3, 4, 4, 6, 5, 5, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 8, 7, 8, 8, 8, 8, 8, 8, 9, 8, 8, 8, 9, 9, 8, 9, 9, 9, 10, 9, 9, 9, 10, 9, 9, 9, 9, 9, 10, 9, 9, 10, 10, 10, 11, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10

Offset: 1

N. J. A. Sloane, Dec 16 2010

nonn

Computed by Alan Wechsler, Dec 16 2010.
Richard C. Schroeppel also asked about the analogous sequence giving the last occurrence of denominator n.
The first occurrence of k in this sequence is apparently at n = A135510(k-1), except for k=5. The last occurrence of k is at n = Fibonacci(k). - Andrey Zabolotskiy, Dec 01 2024

			Start with a pair of fractions 0/1, 1/1 and repeatedly insert the "Farey sum" (p+r)/(q+s) in between every pair of adjacent fractions p/q, r/s. The first few iterations are:
1:   0/1                                     1/1
2:   0/1                 1/2                 1/1
3:   0/1       1/3       1/2       2/3       1/1
4:   0/1  1/4  1/3  2/5  1/2  3/5  2/3  3/4  1/1
We only look at the denominators in this table (which form the sequence A049456, or A002487 if the rightmost column is removed).
1 first appears in row 1, so a(1) = 1.
2 first appears in row 2, so a(2) = 2.
3 first appears in row 3, so a(3) = 3.
4 and 5 first appear in row 4, so a(4) = a(5) = 4.

Based on a posting by Richard C. Schroeppel to the Math Fun Mailing List, Dec 15 2010.

Bo Gyu Jeong, Table of n, a(n) for n = 1..10000
Richard J. Mathar, The Kepler binary tree of reduced fractions, 2017.

See A178047 for another version. Cf. A002487, A006842, A006843, A177903, A178042, A135510.

More terms from Bo Gyu Jeong, Oct 20 2012

A178047 Consider the Farey tree A049455/A049456; a(n) = row at which the denominator n first appears (assumes first row is labeled row 0).

Original entry on oeis.org

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

Offset: 1

N. J. A. Sloane, Dec 16 2010

nonn

Equals A178031 - 1. See that entry for further information.

Richard J. Mathar, The Kepler binary tree of reduced fractions, 2017.

Cf. A295783 (frequencies of this).

A094968 Indices of Fibonacci numbers in Stern's diatomic series A049456 regarded as a single linear sequence.

Original entry on oeis.org

1, 4, 7, 14, 25, 48, 91, 178, 349, 692, 1375, 2742, 5473, 10936, 21859, 43706, 87397, 174780, 349543, 699070, 1398121, 2796224, 5592427, 11184834, 22369645, 44739268, 89478511, 178956998, 357913969, 715827912, 1431655795, 2863311562

Offset: 0

Paul Barry, May 26 2004

By definition, A049456(a(n))=Fib(n+2).

The rank of Fib(n+2) in row n of A049456 (regarded as an irregular triangle read by rows) is A128209(n) = A001045(n)+1. [Comment edited by N. J. A. Sloane, Nov 23 2016]

Colin Barker, Table of n, a(n) for n = 0..1000
D. H. Lehmer, On Stern's Diatomic Series, Amer. Math. Monthly 36(1) 1929, pp. 59-67.
Index entries for linear recurrences with constant coefficients, signature (3,-1,-3,2).

Cf. A000045, A001045, A049456, A128209.

Vec((1 + x - 4*x^2) / ((1 - x)^2*(1 + x)*(1 - 2*x)) + O(x^30)) \\ Colin Barker, Sep 29 2017

G.f. : (1+x-4*x^2) / ((1-x)*(1-x^2)*(1-2*x)).
a(n) = 2^n + n + Jacobsthal(n).
a(n) = A006127(n) + A001045(n).
From Colin Barker, Sep 29 2017: (Start)
a(n) = ((-1)^(1+n) + 2^(2+n) + 3*n) / 3.
a(n) = 3*a(n-1) - a(n-2) - 3*a(n-3) + 2*a(n-4) for n>3.
(End)

A002487 Stern's diatomic series (or Stern-Brocot sequence): a(0) = 0, a(1) = 1; for n > 0: a(2n) = a(n), a(2n+1) = a(n) + a(n+1).

Original entry on oeis.org

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

Offset: 0

N. J. A. Sloane

Also called fusc(n) [Dijkstra].
a(n)/a(n+1) runs through all the reduced nonnegative rationals exactly once [Stern; Calkin and Wilf].
If the terms are written as an array:
  column 0 1 2 3 4 5 6 7 8 9 ...
  row 0: 0
  row 1: 1
  row 2: 1,2
  row 3: 1,3,2,3
  row 4: 1,4,3,5,2,5,3,4
  row 5: 1,5,4,7,3,8,5,7,2,7,5,8,3,7,4,5
  row 6: 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,...
  ...
then (ignoring row 0) the sum of the k-th row is 3^(k-1), each column is an arithmetic progression and the steps are nothing but the original sequence. - Takashi Tokita (butaneko(AT)fa2.so-net.ne.jp), Mar 08 2003
From N. J. A. Sloane, Oct 15 2017: (Start)
The above observation can be made more precise. Let A(n,k), n >= 0, 0 <= k <= 2^(n-1)-1 for k > 0, denote the entry in row n and column k of the left-justified array above.
The equations for columns 0,1,2,3,4,... are successively (ignoring row 0):
     1 (n >= 1),
     n (n >= 2),
   n-1 (n >= 3),
  2n-3 (n >= 3),
   n-2 (n >= 4),
  3n-7 (n >= 4),
  ...
and in general column k > 0 is given by
A(n,k) = a(k)*n - A156140(k) for n >= ceiling(log_2(k+1))+1, and 0 otherwise.
(End)
a(n) is the number of odd Stirling numbers S_2(n+1, 2r+1) [Carlitz].
Moshe Newman proved that the fraction a(n+1)/a(n+2) can be generated from the previous fraction a(n)/a(n+1) = x by 1/(2*floor(x) + 1 - x). The successor function f(x) = 1/(floor(x) + 1 - frac(x)) can also be used.
a(n+1) = number of alternating bit sets in n [Finch].
If f(x) = 1/(1 + floor(x) - frac(x)) then f(a(n-1)/a(n)) = a(n)/a(n+1) for n >= 1. If T(x) = -1/x and f(x) = y, then f(T(y)) = T(x) for x > 0. - Michael Somos, Sep 03 2006
a(n+1) is the number of ways of writing n as a sum of powers of 2, each power being used at most twice (the number of hyperbinary representations of n) [Carlitz; Lind].
a(n+1) is the number of partitions of the n-th integer expressible as the sum of distinct even-subscripted Fibonacci numbers (= A054204(n)), into sums of distinct Fibonacci numbers [Bicknell-Johnson, theorem 2.1].
a(n+1) is the number of odd binomial(n-k, k), 0 <= 2*k <= n. [Carlitz], corrected by Alessandro De Luca, Jun 11 2014
a(2^k) = 1. a(3*2^k) = a(2^(k+1) + 2^k) = 2. Sequences of terms between a(2^k) = 1 and a(2^(k+1)) = 1 are palindromes of length 2^k-1 with a(2^k + 2^(k-1)) = 2 in the middle. a(2^(k-1) + 1) = a(2^k - 1) = k+1 for k > 1. - Alexander Adamchuk, Oct 10 2006
The coefficients of the inverse of the g.f. of this sequence form A073469 and are related to binary partitions A000123. - Philippe Flajolet, Sep 06 2008
It appears that the terms of this sequence are the number of odd entries in the diagonals of Pascal's triangle at 45 degrees slope. - Javier Torres (adaycalledzero(AT)hotmail.com), Aug 06 2009
Let M be an infinite lower triangular matrix with (1, 1, 1, 0, 0, 0, ...) in every column shifted down twice:
   1;
   1, 0;
   1, 1, 0;
   0, 1, 0, 0;
   0, 1, 1, 0, 0;
   0, 0, 1, 0, 0, 0;
   0, 0, 1, 1, 0, 0, 0;
   ...
   Then this sequence A002487 (without initial 0) is the first column of lim_{n->oo} M^n. (Cf. A026741.) - Gary W. Adamson, Dec 11 2009 [Edited by M. F. Hasler, Feb 12 2017]
Member of the infinite family of sequences of the form a(n) = a(2*n); a(2*n+1) = r*a(n) + a(n+1), r = 1 for A002487 = row 1 in the array of A178239. - Gary W. Adamson, May 23 2010
Equals row 1 in an infinite array shown in A178568, sequences of the form
a(2*n) = r*a(n), a(2*n+1) = a(n) + a(n+1); r = 1. - Gary W. Adamson, May 29 2010
Row sums of A125184, the Stern polynomials. Equivalently, B(n,1), the n-th Stern polynomial evaluated at x = 1. - T. D. Noe, Feb 28 2011
The Kn1y and Kn2y triangle sums, see A180662 for their definitions, of A047999 lead to the sequence given above, e.g., Kn11(n) = A002487(n+1) - A000004(n), Kn12(n) = A002487(n+3) - A000012(n), Kn13(n) = A002487(n+5) - A000034(n+1) and Kn14(n) = A002487(n+7) - A157810(n+1). For the general case of the knight triangle sums see the Stern-Sierpiński triangle A191372. This triangle not only leads to Stern's diatomic series but also to snippets of this sequence and, quite surprisingly, their reverse. - Johannes W. Meijer, Jun 05 2011
Maximum of terms between a(2^k) = 1 and a(2^(k+1)) = 1 is the Fibonacci number F(k+2). - Leonid Bedratyuk, Jul 04 2012
Probably the number of different entries per antidiagonal of A223541. That would mean there are exactly a(n+1) numbers that can be expressed as a nim-product 2^x*2^y with x + y = n. - Tilman Piesk, Mar 27 2013
Let f(m,n) be the frequency of the integer n in the interval [a(2^(m-1)), a(2^m-1)]. Let phi(n) be Euler's totient function (A000010). Conjecture: for all integers m,n n<=m f(m,n) = phi(n). - Yosu Yurramendi, Sep 08 2014
Back in May 1995, it was proved that A000360 is the modulo 3 mapping, (+1,-1,+0)/2, of this sequence A002487 (without initial 0). - M. Jeremie Lafitte (Levitas), Apr 24 2017
Define a sequence chf(n) of Christoffel words over an alphabet {-,+}: chf(1) = '-'; chf(2*n+0) = negate(chf(n)); chf(2*n+1) = negate(concatenate(chf(n),chf(n+1))). Then the length of the chf(n) word is fusc(n) = a(n); the number of '-'-signs in the chf(n) word is c-fusc(n) = A287729(n); the number of '+'-signs in the chf(n) word is s-fusc(n) = A287730(n). See examples below. - I. V. Serov, Jun 01 2017
The sequence can be extended so that a(n) = a(-n), a(2*n) = a(n), a(2*n+1) = a(n) + a(n+1) for all n in Z. - Michael Somos, Jun 25 2019
Named after the German mathematician Moritz Abraham Stern (1807-1894), and sometimes also after the French clockmaker and amateur mathematician Achille Brocot (1817-1878). - Amiram Eldar, Jun 06 2021
It appears that a(n) is equal to the multiplicative inverse of A007305(n+1) mod A007306(n+1).  For example, a(12) is 2, the multiplicative inverse of A007305(13) mod A007306(13), where A007305(13) is 4 and A007306(13) is 7. - Gary W. Adamson, Dec 18 2023

			Stern's diatomic 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,
  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,...
  ...
a(91) = 19, because 91_10 = 1011011_2; b_6=b_4=b_3=b_1=b_0=1, b_5=b_2=0;  L=5; m_1=0, m_2=1, m_3=3, m_4=4, m_5=6; c_1=2, c_2=3, c_3=2, c_4=3; f(1)=1, f(2)=2, f(3)=5, f(4)=8, f(5)=19. - _Yosu Yurramendi_, Jul 13 2016
From _I. V. Serov_, Jun 01 2017: (Start)
a(n) is the length of the Christoffel word chf(n):
n  chf(n) A070939(n)   a(n)
1   '-'       1          1
2   '+'       2          1
3   '+-'      2          2
4   '-'       3          1
5   '--+'     3          3
6   '-+'      3          2
... (End)
G.f. = x + x^2 + 2*x^3 + x^4 + 3*x^5 + 2*x^6 + 3*x^7 + x^8 + ... - _Michael Somos_, Jun 25 2019

M. Aigner and G. M. Ziegler, Proofs from THE BOOK, 3rd ed., Berlin, Heidelberg, New York: Springer-Verlag, 2004, p. 97.
Elwyn R. Berlekamp, John H. Conway and Richard K. Guy, Winning Ways, Academic Press, NY, 2 vols., 1982, see p. 114.
Krishna Dasaratha, Laure Flapan, Chansoo Lee, Cornelia Mihaila, Nicholas Neumann-Chun, Sarah Peluse and Matthew Stroegeny, A family of multi-dimensional continued fraction Stern sequences, Abtracts Amer. Math. Soc., Vol. 33 (#1, 2012), #1077-05-2543.
Edsger W. Dijkstra, Selected Writings on Computing, Springer, 1982, p. 232 (sequence is called fusc).
F. G. M. Eisenstein, Eine neue Gattung zahlentheoretischer Funktionen, welche von zwei Elementen abhaengen und durch gewisse lineare Funktional-Gleichungen definirt werden, Verhandlungen der Koenigl. Preuss. Akademie der Wiss. Berlin (1850), pp. 36-42, Feb 18, 1850. Werke, II, pp. 705-711.
Graham Everest, Alf van der Poorten, Igor Shparlinski and Thomas Ward, Recurrence Sequences, Amer. Math. Soc., 2003; see esp. p. 255.
Steven R. Finch, Mathematical Constants, Cambridge, 2003, Section 2.16.3; pp. 148-149.
Ronald L. Graham, Donald E. Knuth and Oren Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 117.
Thomas Koshy, Fibonacci and Lucas numbers with applications, Wiley, 2001, p. 98.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 0..10000
Boris Adamczewski, Non-converging continued fractions related to the Stern diatomic sequence, Acta Arithm. 142 (1) (2010) 67-78.
Jean-Paul Allouche and Michel Mendès France, Lacunary formal power series and the Stern-Brocot sequence, arXiv preprint arXiv:1202.0211 [math.NT], 2012-2013. - _N. J. A. Sloane_, May 10 2012
Jean-Paul Allouche, On the Stern sequence and its twisted version, arXiv preprint arXiv:1202.4171 [math.NT], 2012.
Jean-Paul Allouche, Michel Mendès France, Anna Lubiw, Alfred J. van der Poorten and Jeffrey Shallit, Convergents of folded continued fractions.
Jean-Paul Allouche and Jeffrey Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197. [Preprint.]
Jean-Paul Allouche and Jeffrey Shallit, The ring of k-regular sequences, II, Theoret. Computer Sci., 307 (2003), 3-29. [Preprint.]
Michael Baake and Michael Coons, A natural probability measure derived from Stern's diatomic sequence, arXiv:1706.00187 [math.NT], 2017.
Roland Bacher, Twisting the Stern sequence, arXiv:1005.5627 [math.CO], 2010.
Bruce Bates, Martin Bunder and Keith Tognetti, Linking the Calkin-Wilf and Stern-Brocot trees, Eur. J. Comb., Vol. 31, No. 7 (2010), pp. 1637-1661.
Bruce Bates and Toufik Mansour, The q-Calkin-Wilf tree, Journal of Combinatorial Theory Series A, Vol. 118, No. 3 (2011), pp. 1143-1151.
Marjorie Bicknell-Johnson, Stern's Diatomic Array Applied to Fibonacci Representations, Fibonacci Quarterly, Vol. 41 (2003), pp. 169-180.
Arie Bos, Graph connecting p/q and r/s where |q*r-p*s|=1 and p=a(n), q= a(n+1), r=a(m), s=a(m+1) and 0<=p/q,r/s<=1.
Richard P. Brent, Michael Coons and Wadim Zudilin, Asymptotics of a Mahler Function, Slides of talk presented at AustMS/NZMS 2014, Melbourne, 8 December 2014.
Neil Calkin and Herbert S. Wilf, Recounting the rationals, Amer. Math. Monthly, Vol. 107, No. 4 (2000), pp. 360-363.
L. Carlitz, A problem in partitions related to the Stirling numbers, Bull. Amer. Math. Soc., Vol. 70, No. 2 (1964), pp. 275-278. [Abstract.]
L. Carlitz, A problem in partitions related to the Stirling numbers, Riv. Mat. Univ. Parma, (2) 5 (1964), 61-75.
Michael Coons, The transcendence of series related to Stern's diatomic sequence, International Journal of Number Theory 6.01 (2010): 211-217.
Michael Coons, On some conjectures concerning Stern's sequence and its twist, Integers 11.6 (2011): 775-789.
Michael Coons, A Correlation Identity for Stern's Sequence, Integers 12.3 (2012): 459-464.
Michael Coons and Jeffrey Shallit, A pattern sequence approach to Stern's sequence, Discrete Math., Vol. 311 (2011), pp. 2630-2633.
Michael Coons and Jason Tyler, The maximal order of Stern's diatomic sequence, arXiv:1307.1521 [math.NT], 2013-2014.
Kevin M. Courtright and James A. Sellers, Arithmetic Properties for Hyper m-ary Partitions, INTEGERS, Vol. 4 (2004), Article A6.
Valerio De Angelis, The Stern diatomic sequence via generalized Chebyshev polynomials, American Mathematical Monthly 124.5 (2017): 451-455. See also, arXiv:1511.02422 [math.NT], 2015.
Philip de Castro et al., Counting binomial coefficients divisible by a prime power, Amer. Math. Monthly, Vol. 125, No. 6 (2018), pp. 531-540. See Table p. 534.
Colin Defant, Upper Bounds for Stern's Diatomic Sequence and Related Sequences, Electronic Journal of Combinatorics, Vol. 23, No. 4 (2016), #P4.8.
Georges De Rham, Un peu de mathématiques à propos d'une courbe plane, Elemente der Math., Vol. 2 (1947), pp. 73-76 and 89-97.
Marc Deléglise, Paul Erdős and Jean-Louis Nicolas, Sur les ensembles représentés par les partitions d'un entier n [Sets represented by partitions of an integer n] Paul Erdős memorial collection. Discrete Math., Vol. 200, No. 1-3 (1999), pp. 27-48. MR1692277 (2000e:05012). See Table 1. _N. J. A. Sloane_, Mar 18 2012
Edsger W. Dijkstra, An exercise for Dr. R. M. Burstall.
Edsger W. Dijkstra, More about the function "fusc".
Karl Dilcher and Larry Ericksen, Hyperbinary expansions and Stern polynomials, Elec. J. Combin, Vol. 22 (2015), #P2.24.
Karl Dilcher and Larry Ericksen, Factors and irreducibility of generalized Stern polynomials, Integers, Vol. 15 (2015), #A50.
Karl Dilcher and Larry Ericksen, Continued fractions and Stern polynomials, Ramanujan Journal, Vol. 45 (2017), pp. 659-681.
Karl Dilcher and Larry Ericksen, Polynomials Characterizing Hyper b-ary Representations, J. Int. Seq., Vol. 21 (2018), Article 18.4.3.
Karl Dilcher and Larry Ericksen, Polynomial Analogues of Restricted b-ary Partition Functions, J. Int. Seq., Vol. 22 (2019), Article 19.3.2.
Tom Edgar, On the number of hyper m-ary partitions, Integers, Vol. 18 (2018), Article #A47.
De-Jun Feng, Pierre Liardet and Alain Thomas, Partition functions in numeration systems with bounded multiplicity, Uniform Distribution Theory, Vol. 9, No. 1 (2014).
Steven R. Finch, P. Sebah and Z.-Q. Bai, Odd Entries in Pascal's Trinomial Triangle, arXiv:0802.2654 [math.NT], 2008.
Aviezri S. Fraenkel, Ratwyt, Dec 28 2011.
Thomas Garrity, A multi-dimensional continued fraction generalization of Stern's diatomic sequence, arXiv:1206.6685 [math.CO], 2012-2013.
Thomas Garrity, A multi-dimensional continued fraction generalization of Stern's diatomic sequence, Journal of Integer Sequences, Vol. 16 (2013), #13.7.7.
Michael Gilleland, Some Self-Similar Integer Sequences.
Jose Grimm, Implementation of Bourbaki's Elements of Mathematics in Coq: Part Two, From Natural Numbers to Real Numbers, Journal of Formalized Reasoning, Vol. 9, No. 2 (2016), pp. 1-52; see p. 38.
Brian Hayes, On the Teeth of Wheels, American Scientist, Vol. 88, No. 4 (July-August 2000), pp. 296-300 (5 pages).
Andreas M. Hinz, Sandi Klavžar, Uroš Milutinović and Ciril Petr,, The Tower of Hanoi - Myths and Maths, Birkhäuser 2013. See page 115. Book's website
Andreas M. Hinz, Sandi Klavžar, Uroš Milutinović, Daniele Parisse and Ciril Petr, Metric properties of the Tower of Hanoi graphs and Stern's diatomic sequence European J. Combin., Vol. 26, No. 5 (2005), pp. 693-708.
Johannes Kepler, Harmonices Mundi, Vol. III (1619) p.27.
Donald E. Knuth, C. P. Rupert, Alex Smith and Richard Stong, Recounting the Rationals, Continued: 10906, solution by Moshe Newman, American Mathematical Monthly, Vol. 110, No. 7 (2003), pp. 642-643.
Jennifer Lansing, Distribution of Values of the Binomial Coefficients and the Stern Sequence, Journal of Integer Sequences, Vol. 16 (2013), Article 13.3.7.
Jennifer Lansing, Largest Values for the Stern Sequence, Journal of Integer Sequences, Vol. 17 (2014), Article 14.7.5.
D. H. Lehmer, On Stern's Diatomic Series, Amer. Math. Monthly, Vol. 36, No. 1 (1929), pp. 59-67. [Annotated and corrected scanned copy.]
Julien Leroy, Michel Rigo and Manon Stipulanti, Counting the number of non-zero coefficients in rows of generalized Pascal triangles, Discrete Mathematics, Vol. 340 (2017), pp. 862-881. Also available at Université de Liège.
Peter Luschny, Rational Trees and Binary Partitions.
Alan J. Macfarlane, Linear reversible second-order cellular automata and their first-order matrix equivalents, Journal of Physics A: Mathematical and General 37.45 (2004): 10791. See Fig. 2.
Laura Monroe, Binary Signed-Digit Integers, the Stern Diatomic Sequence and Stern Polynomials, arXiv:2103.05810 [math.NT], 2021.
Sam Northshield, Stern's diatomic sequence 0, 1, 1, 2, 1, 3, 2, 3, 1, 4, ..., Amer. Math. Monthly, Vol. 117, No. 7 (2010), pp. 581-598.
Sam Northshield, An Analogue of Stern's Sequence for Z[sqrt(2)], Journal of Integer Sequences, Vol. 18 (2015), Article 15.11.6.
Sam Northshield, Re^3counting the Rationals, arXiv:1905.10369 [math.NT], 2019.
Project Euler, Problem 169 - Exploring the number of different ways a number can be expressed as a sum of powers of 2.
Bruce Reznick, Some binary partition functions, in "Analytic number theory" (Conf. in honor P. T. Bateman, Allerton Park, IL, 1989), Progr. Math., 85, Birkhäuser Boston, Boston, MA, 1990, pp. 451-477.
Bruce Reznick, Regularity properties of the Stern enumeration of the Rationals, Journal of Integer Sequences, Vol. 11 (2008) Article 08.4.1.
Jürgen W. Sander, Jörn Steuding and Rasa Steuding, Diophantine aspects of the Calkin-Wilf iteration, El. Math., Vol. 66, No. 2 (2011) pp. 45-55. doi:10.4171/EM/170.
Anton Shakov, Polynomials in Z[x] whose divisors are enumerated by SL_2(N_0), arXiv:2405.03552 [math.NT], 2024. See p. 27.
Rémy Sigrist, Nonperiodic tilings related to Stern's diatomic series and based on tiles decorated with elements of F_p, arXiv:2301.06039 [math.CO], 2023.
N. J. A. Sloane, Stern-Brocot or Farey Tree.
N. J. A. Sloane and Brady Haran, Amazing Graphs III, Numberphile video (2019).
Richard P. Stanley and Herbert S. Wilf, Refining the Stern Diatomic Sequence, unpublished.
Richard P. Stanley and Herbert S. Wilf, Refining the Stern Diatomic Sequence [Cached copy, with permission]
Jörn Steuding, Stefanie Hofmann and Gertraud Schuster, Euclid, Calkin & Wilf - playing with rationals, Elemente der Mathematik, Vol. 63, No. 3 (2008), pp. 109-117.
Ralf Stephan, Divide-and-conquer generating functions. I. Elementary sequences, arXiv:math/0307027 [math.CO], 2003.
M. A. Stern, Über eine zahlentheoretische Funktion, J. Reine Angew. Math., Vol. 55 (1858), pp. 193-220.
Maciej Ulas, Arithmetic properties of the sequence of degrees of Stern polynomials and related results, arXiv:1102.5111 [math.CO], 2011.
Maciej Ulas and Oliwia Ulas, On certain arithmetic properties of Stern polynomials, arXiv:1102.5109 [math.CO], 2011.
Igor Urbiha, Some properties of a function studied by De Rham, Carlitz and Dijkstra and its relation to the (Eisenstein -) Stern's diatomic sequence, Math. Commun., Vol. 6 (2002), pp. 181-198.
Eric Weisstein's World of Mathematics, Calkin-Wilf Tree and Stern's Diatomic Series.
Yasuhisa Yamada, A function from Stern's diatomic sequence, and its properties, arXiv:2004.00278 [math.NT], 2020.
Index entries for "core" sequences
Index entries for fraction trees
Index entries for sequences related to enumerating the rationals
Index entries for sequences related to Stern's sequences
Index entries for sequences related to trees

Cf. A000120, A000123, A000360, A001045, A002083, A011655, A020950, A026741, A037227, A046815, A070871, A070872, A071883, A073459, A084091, A101624, A126606, A168081, A174980, A174981, A178239, A178568, A212288, A213369, A260443, A277020, A277325, A287729, A287730, A293160.
Record values are in A212289.
If the 1's are replaced by pairs of 1's we obtain A049456.
Inverse: A020946.
Cf. a(A001045(n)) = A000045(n). a(A062092(n)) = A000032(n+1).
Cf. A064881-A064886 (Stern-Brocot subtrees).
A column of A072170.
Cf. A049455 for the 0,1 version of Stern's diatomic array.
Cf. A000119, A262097 for analogous sequences in other bases and A277189, A277315, A277328 for related sequences with similar graphs.
Cf. A086592 and references therein to other sequences related to Kepler's tree of fractions.

a002487 n = a002487_list !! n
a002487_list = 0 : 1 : stern [1] where
   stern fuscs = fuscs' ++ stern fuscs' where
     fuscs' = interleave fuscs $ zipWith (+) fuscs $ (tail fuscs) ++ [1]
   interleave []     ys = ys
   interleave (x:xs) ys = x : interleave ys xs
-- Reinhard Zumkeller, Aug 23 2011

using Nemo
function A002487List(len)
    a, A = QQ(0), [0,1]
    for n in 1:len
        a = next_calkin_wilf(a)
        push!(A, denominator(a))
    end
A end
A002487List(91) |> println # Peter Luschny, Mar 13 2018

[&+[(Binomial(k, n-k-1) mod 2): k in [0..n]]: n in [0..100]]; // Vincenzo Librandi, Jun 18 2019

A002487 := proc(n) option remember; if n <= 1 then n elif n mod 2 = 0 then procname(n/2); else procname((n-1)/2)+procname((n+1)/2); fi; end: seq(A002487(n),n=0..91);
A002487 := proc(m) local a,b,n; a := 1; b := 0; n := m; while n>0 do if type(n,odd) then b := a+b else a := a+b end if; n := floor(n/2); end do; b; end proc: seq(A002487(n),n=0..91); # Program adapted from E. Dijkstra, Selected Writings on Computing, Springer, 1982, p. 232. - Igor Urbiha (urbiha(AT)math.hr), Oct 28 2002. Since A007306(n) = a(2*n+1), this program can be adapted for A007306 by replacing b := 0 by b := 1.
A002487 := proc(n::integer) local k; option remember; if n = 0 then 0 elif n=1 then 1 else add(K(k,n-1-k)*procname(n - k), k = 1 .. n) end if end proc:
K := proc(n::integer, k::integer) local KC; if 0 <= k and k <= n and n-k <= 2 then KC:=1; else KC:= 0; end if; end proc: seq(A002487(n),n=0..91); # Thomas Wieder, Jan 13 2008
# next Maple program:
a:= proc(n) option remember; `if`(n<2, n,
      (q-> a(q)+(n-2*q)*a(n-q))(iquo(n, 2)))
    end:
seq(a(n), n=0..100);  # Alois P. Heinz, Feb 11 2021
fusc := proc(n) local a, b, c; a := 1; b := 0;
    for c in convert(n, base, 2) do
        if c = 0 then a := a + b else b := a + b fi od;
    b end:
seq(fusc(n), n = 0..91); # Peter Luschny, Nov 09 2022
Stern := proc(n, u) local k, j, b;
    b := j -> nops({seq(Bits:-Xor(k, j-k), k = 0..j)}):
    ifelse(n=0, 1-u, seq(b(j), j = 2^(n-1)-1..2^n-1-u)) end:
seq(print([n], Stern(n, 1)), n = 0..5); # As shown in the comments.
seq(print([n], Stern(n, 0)), n = 0..5); # As shown in the examples. # Peter Luschny, Sep 29 2024

a[0] = 0; a[1] = 1; a[n_] := If[ EvenQ[n], a[n/2], a[(n-1)/2] + a[(n+1)/2]]; Table[ a[n], {n, 0, 100}] (* end of program *)
Onemore[l_] := Transpose[{l, l + RotateLeft[l]}] // Flatten;
NestList[Onemore, {1}, 5] // Flatten  (*gives [a(1), ...]*) (* Takashi Tokita, Mar 09 2003 *)
ToBi[l_] := Table[2^(n - 1), {n, Length[l]}].Reverse[l]; Map[Length,
Split[Sort[Map[ToBi, Table[IntegerDigits[n - 1, 3], {n, 500}]]]]]  (*give [a(1), ...]*) (* Takashi Tokita, Mar 10 2003 *)
A002487[m_] := Module[{a = 1, b = 0, n = m}, While[n > 0, If[OddQ[n], b = a+b, a = a+b]; n = Floor[n/2]]; b]; Table[A002487[n], {n, 0, 100}] (* Jean-François Alcover, Sep 06 2013, translated from 2nd Maple program *)
a[0] = 0; a[1] = 1;
Flatten[Table[{a[2*n] = a[n], a[2*n + 1] = a[n] + a[n + 1]}, {n, 0, 50}]] (* Horst H. Manninger, Jun 09 2021 *)
nmax = 100; CoefficientList[Series[x*Product[(1 + x^(2^k) + x^(2^(k+1))), {k, 0, Floor[Log[2, nmax]] + 1}], {x, 0, nmax}], x] (* Vaclav Kotesovec, Oct 08 2022 *)

{a(n) = n=abs(n); if( n<2, n>0, a(n\2) + if( n%2, a(n\2 + 1)))};

fusc(n)=local(a=1,b=0);while(n>0,if(bitand(n,1),b+=a,a+=b);n>>=1);b \\ Charles R Greathouse IV, Oct 05 2008

A002487(n,a=1,b=0)=for(i=0,logint(n,2),if(bittest(n,i),b+=a,a+=b));b \\ M. F. Hasler, Feb 12 2017, updated Feb 14 2019

from functools import lru_cache
@lru_cache(maxsize=None)
def a(n): return n if n<2 else a(n//2) if n%2==0 else a((n - 1)//2) + a((n + 1)//2) # Indranil Ghosh, Jun 08 2017; corrected by Reza K Ghazi, Dec 27 2021

def a(n):
    a, b = 1, 0
    while n > 0:
        if n & 1:
            b += a
        else:
            a += b
        n >>= 1
    return b
# Reza K Ghazi, Dec 29 2021

def A002487(n): return sum(int(not (n-k-1) & ~k) for k in range(n)) # Chai Wah Wu, Jun 19 2022

# (fast way for big vectors)
from math import log, ceil
import numpy
how_many_terms = 2**20  # (Powers of 2 recommended but other integers are also possible.)
A002487, A002487[1]  = numpy.zeros(2**(ce:=ceil(log(how_many_terms,2))), dtype=object), 1
for exponent in range(1,ce):
    L, L2 = 2**exponent, 2**(exponent+1)
    A002487[L2 - 1] = exponent + 1
    A002487[L:L2][::2] = A002487[L >> 1: L]
    A002487[L + 1:L2 - 2][::2] = A002487[L:L2 - 3][::2]  +  A002487[L + 2:L2 - 1][::2]
print(list(A002487[0:100])) # Karl-Heinz Hofmann, Jul 22 2025

N <- 50 # arbitrary
a <- 1
for (n in 1:N)
{
  a[2*n    ] = a[n]
  a[2*n + 1] = a[n] + a[n+1]
  a
}
a
# Yosu Yurramendi, Oct 04 2014

# Given n, compute a(n) by taking into account the binary representation of n
a <- function(n){
  b <- as.numeric(intToBits(n))
  l <- sum(b)
  m <- which(b == 1)-1
  d <- 1
  if(l > 1) for(j in 1:(l-1)) d[j] <- m[j+1]-m[j]+1
  f <- c(0,1)
  if(l > 1) for(j in 3:(l+1)) f[j] <- d[j-2]*f[j-1]-f[j-2]
  return(f[l+1])
} # Yosu Yurramendi, Dec 13 2016

# computes the sequence as a vector A, rather than function a() as above.
A <- c(1,1)
maxlevel <- 5 # by choice
for(m in 1:maxlevel) {
  A[2^(m+1)] <- 1
  for(k in 1:(2^m-1)) {
    r <- m - floor(log2(k)) - 1
    A[2^r*(2*k+1)] <- A[2^r*(2*k)] + A[2^r*(2*k+2)]
}}
A # Yosu Yurramendi, May 08 2018

def A002487(n):
    M = [1, 0]
    for b in n.bits():
        M[b] = M[0] + M[1]
    return M[1]
print([A002487(n) for n in (0..91)])
# For a dual see A174980. Peter Luschny, Nov 28 2017

;; An implementation of memoization-macro definec can be found for example in: http://oeis.org/wiki/Memoization
(definec (A002487 n) (cond ((<= n 1) n) ((even? n) (A002487 (/ n 2))) (else (+ (A002487 (/ (- n 1) 2)) (A002487 (/ (+ n 1) 2))))))
;; Antti Karttunen, Nov 05 2016

a(n+1) = (2*k+1)*a(n) - a(n-1) where k = floor(a(n-1)/a(n)). - David S. Newman, Mar 04 2001
Let e(n) = A007814(n) = exponent of highest power of 2 dividing n. Then a(n+1) = (2k+1)*a(n)-a(n-1), n > 0, where k = e(n). Moreover, floor(a(n-1)/a(n)) = e(n), in agreement with D. Newman's formula. - Dragutin Svrtan (dsvrtan(AT)math.hr) and Igor Urbiha (urbiha(AT)math.hr), Jan 10 2002
Calkin and Wilf showed 0.9588 <= limsup a(n)/n^(log(phi)/log(2)) <= 1.1709 where phi is the golden mean. Does this supremum limit = 1? - Benoit Cloitre, Jan 18 2004.  Coons and Tyler show the limit is A246765 = 0.9588... - Kevin Ryde, Jan 09 2021
a(n) = Sum_{k=0..floor((n-1)/2)} (binomial(n-k-1, k) mod 2). - Paul Barry, Sep 13 2004
a(n) = Sum_{k=0..n-1} (binomial(k, n-k-1) mod 2). - Paul Barry, Mar 26 2005
G.f. A(x) satisfies 0 = f(A(x), A(x^2), A(x^4)) where f(u, v, w) = v^3 + 2*u*v*w - u^2*w. - Michael Somos, May 02 2005
G.f. A(x) satisfies 0 = f(A(x), A(x^2), A(x^3), A(x^6)) where f(u1, u2, u3, u6) = u1^3*u6 - 3*u1^2*u2*u6 + 3*u2^3*u6 - u2^3*u3. - Michael Somos, May 02 2005
G.f.: x * Product_{k>=0} (1 + x^(2^k) + x^(2^(k+1))) [Carlitz].
a(n) = a(n-2) + a(n-1) - 2*(a(n-2) mod a(n-1)). - Mike Stay, Nov 06 2006
A079978(n) = (1 + e^(i*Pi*A002487(n)))/2, i=sqrt(-1). - Paul Barry, Jan 14 2005
a(n) = Sum_{k=1..n} K(k, n-k)*a(n - k), where K(n,k) = 1 if 0 <= k AND k <= n AND n-k <= 2 and K(n,k) = 0 else. (When using such a K-coefficient, several different arguments to K or several different definitions of K may lead to the same integer sequence. For example, if we drop the condition k <= n in the above definition, then we arrive at A002083 = Narayana-Zidek-Capell numbers.) - Thomas Wieder, Jan 13 2008
a(k+1)*a(2^n - k) - a(k)*a(2^n - (k+1)) = 1; a(2^n - k) + a(k) = a(2^(n+1) + k). Both formulas hold for 0 <= k <= 2^n - 1. G.f.: G(z) = a(1) + a(2)*z + a(3)*z^2 + ... + a(k+1)*z^k + ... Define f(z) = (1 + z + z^2), then G(z) = lim f(z)*f(z^2)*f(z^4)* ... *f(z^(2^n))*... = (1 + z + z^2)*G(z^2). - Arie Werksma (werksma(AT)tiscali.nl), Apr 11 2008
a(k+1)*a(2^n - k) - a(k)*a(2^n - (k+1)) = 1 (0 <= k <= 2^n - 1). - Arie Werksma (werksma(AT)tiscali.nl), Apr 18 2008
a(2^n + k) = a(2^n - k) + a(k) (0 <= k <= 2^n). - Arie Werksma (werksma(AT)tiscali.nl), Apr 18 2008
Let g(z) = a(1) + a(2)*z + a(3)*z^2 + ... + a(k+1)*z^k + ..., f(z) = 1 + z + z^2. Then g(z) = lim_{n->infinity} f(z)*f(z^2)*f(z^4)*...*f(z^(2^n)), g(z) = f(z)*g(z^2). - Arie Werksma (werksma(AT)tiscali.nl), Apr 18 2008
For 0 <= k <= 2^n - 1, write k = b(0) + 2*b(1) + 4*b(2) + ... + 2^(n-1)*b(n-1) where b(0), b(1), etc. are 0 or 1. Define a 2 X 2 matrix X(m) with entries x(1,1) = x(2,2) = 1, x(1,2) = 1 - b(m), x(2,1) = b(m). Let P(n)= X(0)*X(1)* ... *X(n-1). The entries of the matrix P are members of the sequence: p(1,1) = a(k+1), p(1,2) = a(2^n - (k+1)), p(2,1) = a(k), p(2,2) = a(2^n - k). - Arie Werksma (werksma(AT)tiscali.nl), Apr 20 2008
Let f(x) = A030101(x); if 2^n + 1 <= x <= 2^(n + 1) and y = 2^(n + 1) - f(x - 1) then a(x) = a(y). - Arie Werksma (Werksma(AT)Tiscali.nl), Jul 11 2008
a(n) = A126606(n + 1) / 2. - Reikku Kulon, Oct 05 2008
Equals infinite convolution product of [1,1,1,0,0,0,0,0,0] aerated A000079 - 1 times, i.e., [1,1,1,0,0,0,0,0,0] * [1,0,1,0,1,0,0,0,0] * [1,0,0,0,1,0,0,0,1]. - Mats Granvik and Gary W. Adamson, Oct 02 2009; corrected by Mats Granvik, Oct 10 2009
a(2^(p+2)*n+2^(p+1)-1) - a(2^(p+1)*n+2^p-1) = A007306(n+1), p >= 0 and n >= 0. - Johannes W. Meijer, Feb 07 2013
a(2*n-1) = A007306(n), n > 0. - Yosu Yurramendi, Jun 23 2014
a(n*2^m) = a(n), m>0, n > 0. - Yosu Yurramendi, Jul 03 2014
a(k+1)*a(2^m+k) - a(k)*a(2^m+(k+1)) = 1 for m >= 0, 0 <= k < 2^m. - Yosu Yurramendi, Nov 07 2014
a(2^(m+1)+(k+1))*a(2^m+k) - a(2^(m+1)+k)*a(2^m+(k+1)) = 1 for m >= 0, 0 <= k < 2^m. - Yosu Yurramendi, Nov 07 2014
a(5*2^k) = 3. a(7*2^k) = 3. a(9*2^k) = 4. a(11*2^k) = 5. a(13*2^k) = 5. a(15*2^k) = 4. In general: a((2j-1)*2^k) = A007306(j), j > 0, k >= 0 (see Adamchuk's comment). - Yosu Yurramendi, Mar 05 2016
a(2^m+2^m'+k') = a(2^m'+k')*(m-m'+1) - a(k'), m >= 0, m' <= m-1, 0 <= k' < 2^m'. - Yosu Yurramendi, Jul 13 2016
From Yosu Yurramendi, Jul 13 2016: (Start)
Let n be a natural number and [b_m b_(m-1) ... b_1 b_0] its binary expansion with b_m=1.
Let L = Sum_{i=0..m} b_i be the number of binary digits equal to 1 (L >= 1).
Let {m_j: j=1..L} be the set of subindices such that b_m_j = 1, j=1..L, and 0 <= m_1 <= m_2 <= ... <= m_L = m.
If L = 1 then c_1 = 1, otherwise let {c_j: j=1..(L-1)} be the set of coefficients such that c_(j) = m_(j+1) - m_j + 1, 1 <= j <= L-1.
Let f be a function defined on {1..L+1} such that f(1) = 0, f(2) = 1, f(j) = c_(j-2)*f(j-1) - f(j-2), 3 <= j <= L+1.
Then a(n) = f(L+1) (see example). (End)
a(n) = A001222(A260443(n)) = A000120(A277020(n)). Also a(n) = A000120(A101624(n-1)) for n >= 1. - Antti Karttunen, Nov 05 2016
(a(n-1) + a(n+1))/a(n) = A037227(n) for n >= 1. - Peter Bala, Feb 07 2017
a(0) = 0; a(3n) = 2*A000360(3n-1); a(3n+1) = 2*A000360(3n) - 1; a(3n+2) = 2*A000360(3n+1) + 1. - M. Jeremie Lafitte (Levitas), Apr 24 2017
From I. V. Serov, Jun 14 2017: (Start)
a(n) = A287896(n-1) - 1*A288002(n-1) for n > 1;
a(n) = A007306(n-1) - 2*A288002(n-1) for n > 1. (End)
From Yosu Yurramendi, Feb 14 2018: (Start)
a(2^(m+2) + 2^(m+1) + k) - a(2^(m+1) + 2^m + k) = 2*a(k), m >= 0, 0 <= k < 2^m.
a(2^(m+2) + 2^(m+1) + k) - a(2^(m+1)       + k) = a(2^m + k), m >= 0, 0 <= k < 2^m.
a(2^m + k) = a(k)*(m - floor(log_2(k)) - 1) + a(2^(floor(log_2(k))+1) + k), m >= 0, 0 < k < 2^m,  a(2^m) = 1, a(0) = 0. (End)
From Yosu Yurramendi, May 08 2018: (Start)
a(2^m) = 1, m >= 0.
a(2^r*(2*k+1)) = a(2^r*(2*k)) + a(2^r*(2*k+2)), r < - m - floor(log_2(k)) - 1, m > 0, 1 <= k < 2^m. (End)
Trow(n) = [card({k XOR (j-k): k=0..j}) for j = 2^(n-1)-1..2^n-2] when regarded as an irregular table (n >= 1). - Peter Luschny, Sep 29 2024
a(n) = A000120(A168081(n)). - Karl-Heinz Hofmann, Jun 16 2025

Additional references and comments from Len Smiley, Joshua Zucker, Rick L. Shepherd and Herbert S. Wilf
Typo in definition corrected by Reinhard Zumkeller, Aug 23 2011
Incorrect formula deleted and text edited by Johannes W. Meijer, Feb 07 2013

A006843 Triangle read by rows: row n gives denominators of Farey series of order n.

Original entry on oeis.org

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

Offset: 1

N. J. A. Sloane

			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, 1/2, 2/3, 3/4, 1/1;
0/1, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 1/1;
... = A006842/A006843.

J. H. Conway and R. K. Guy, The Book of Numbers, Copernicus Press, NY, 1996, p. 152.
Martin Gardner, The Last Recreations, Chapter 12: Strong Laws of Small Primes, Springer-Verlag, 1997, pp. 191-205, especially p. 199.
G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers. 3rd ed., Oxford Univ. Press, 1954, p. 23.
W. J. LeVeque, Topics in Number Theory. Addison-Wesley, Reading, MA, 2 vols., 1956, Vol. 1, p. 154.
A. O. Matveev, Farey Sequences, De Gruyter, 2017.
I. Niven and H. S. Zuckerman, An Introduction to the Theory of Numbers. 2nd ed., Wiley, NY, 1966, p. 141.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 1..10563
R. K. Guy, The strong law of small numbers, Amer. Math. Monthly 95 (1988), no. 8, 697-712. [Annotated scanned copy]
Andrey O. Matveev, Neighboring Fractions in Farey Subsequences, arXiv:0801.1981 [math.NT], 2008-2010.
Andrey O. Matveev, Farey Sequences: Errata + Haskell code
N. J. A. Sloane, Stern-Brocot or Farey Tree
Eric Weisstein's World of Mathematics, Farey Sequence.
Index entries for sequences related to Stern's sequences

Row n has A005728(n) terms. - Michel Marcus, Jun 27 2014
Row sums give A240877.
Cf. A006842 (numerators), A049455, A049456, A007305, A007306.
See also A177405/A177407.

Farey := proc(n) sort(convert(`union`({0},{seq(seq(m/k,m=1..k),k=1..n)}),list)) end: seq(denom(Farey(i)),i=1..5); # Peter Luschny, Apr 28 2009

Farey[n_] := Union[ Flatten[ Join[{0}, Table[a/b, {b, n}, {a, b}]]]]; Flatten[ Table[ Denominator[ Farey[n]], {n, 9}]] (* Robert G. Wilson v, Apr 08 2004 *)
Table[Denominator[FareySequence[n]],{n,10}]//Flatten (* Requires Mathematica version 10 or later *) (* Harvey P. Dale, Oct 04 2016 *)

row(n) = {vf = [0]; for (k=1, n, for (m=1, k, vf = concat(vf, m/k););); vf = vecsort(Set(vf)); for (i=1, #vf, print1(denominator(vf[i]), ", "));} \\ Michel Marcus, Jun 27 2014

More terms from Robert G. Wilson v, Apr 08 2004

Changed offset (=order of first row) to 1 by R. J. Mathar, Apr 26 2009

A006842 Triangle read by rows: row n gives numerators of Farey series of order n.

Original entry on oeis.org

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

Offset: 1

N. J. A. Sloane

			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, 1/2, 2/3, 3/4, 1/1;
0/1, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 1/1;
... = A006842/A006843

A. H. Beiler, Recreations in the Theory of Numbers, Dover, NY, 1964
J. H. Conway and R. K. Guy, The Book of Numbers, Copernicus Press, NY, 1996, p. 152.
L. E. Dickson, History of the Theory of Numbers. Carnegie Institute Public. 256, Washington, DC, Vol. 1, 1919; Vol. 2, 1920; Vol. 3, 1923. See Vol. 1.
Guthery, Scott B. A motif of mathematics. Docent Press, 2011.
G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers. 3rd ed., Oxford Univ. Press, 1954, p. 23.
W. J. LeVeque, Topics in Number Theory. Addison-Wesley, Reading, MA, 2 vols., 1956, Vol. 1, p. 154.
A. O. Matveev, Farey Sequences, De Gruyter, 2017.
I. Niven and H. S. Zuckerman, An Introduction to the Theory of Numbers. 2nd ed., Wiley, NY, 1966, p. 141.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 1..10563
Maxim Bruckheimer and Abraham Arcavi, Farey series and Pick’s area theorem, The Mathematical Intelligencer, 17.4 (1995): 64-67.
Cristian Cobeli and Alexandru Zaharescu, The Haros-Farey sequence at two hundred years, Acta Univ. Apulensis Math. Inform 5 (2003): 1-38.
Andrey O. Matveev, Neighboring Fractions in Farey Subsequences, arXiv:0801.1981 [math.NT], 2008-2010.
Andrey O. Matveev, Farey Sequences: Errata + Haskell code
N. J. A. Sloane, Stern-Brocot or Farey Tree
Eric Weisstein's World of Mathematics, Farey Sequence.
Index entries for sequences related to Stern's sequences

Row n has A005728(n) terms. - Michel Marcus, Jun 27 2014

Cf. A006843 (denominators), A049455, A049456, A007305, A007306. Also A177405/A177407.

Farey := proc(n) sort(convert(`union`({0},{seq(seq(m/k,m=1..k),k=1..n)}),list)) end: seq(numer(Farey(i)),i=1..5); # Peter Luschny, Apr 28 2009

Farey[n_] := Union[ Flatten[ Join[{0}, Table[a/b, {b, n}, {a, b}]]]]; Flatten[ Table[ Numerator[ Farey[n]], {n, 0, 9}]] (* Robert G. Wilson v, Apr 08 2004 *)
Table[FareySequence[n] // Numerator, {n, 1, 9}] // Flatten (* Jean-François Alcover, Sep 25 2018 *)

row(n) = {vf = [0]; for (k=1, n, for (m=1, k, vf = concat(vf, m/k););); vf = vecsort(Set(vf)); for (i=1, #vf, print1(numerator(vf[i]), ", "));} \\ Michel Marcus, Jun 27 2014

More terms from Robert G. Wilson v, Apr 08 2004

A128209 Jacobsthal numbers(A001045) + 1.

Original entry on oeis.org

1, 2, 2, 4, 6, 12, 22, 44, 86, 172, 342, 684, 1366, 2732, 5462, 10924, 21846, 43692, 87382, 174764, 349526, 699052, 1398102, 2796204, 5592406, 11184812, 22369622, 44739244, 89478486, 178956972, 357913942, 715827884, 1431655766, 2863311532, 5726623062

Offset: 0

Paul Barry, Feb 19 2007

Row sums of A128208.
Essentially the same as A052953. - R. J. Mathar, Jun 14 2008
Let I=I_n be the n X n identity matrix and P=P_n be the incidence matrix of the cycle (1,2,3,...,n). Then, for n >= 1, a(n+1) is the number of different representations of matrix P^(-1)+I+P by sum of permutation matrices. - Vladimir Shevelev, Apr 12 2010
a(n) is the rank of Fibonacci(n+2) in row n of A049456 (regarded as an irregular triangle read by rows). - N. J. A. Sloane, Nov 23 2016

V. S. Shevelyov (Shevelev), Extension of the Moser class of four-line Latin rectangles, DAN Ukrainy, 3(1992),15-19. [From Vladimir Shevelev, Apr 12 2010]

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
D. H. Lehmer, On Stern's Diatomic Series, Amer. Math. Monthly 36(1) 1929, pp. 59-67. [Annotated and corrected scanned copy]
Index entries for linear recurrences with constant coefficients, signature (2,1,-2).

Cf. A167030, A153643, A049456.

[1+2^n/3-(-1)^n/3: n in [0..40]]; // Vincenzo Librandi, Aug 11 2011

CoefficientList[Series[(1-3*x^2)/(1-2*x-x^2+2*x^3),{x,0,40}],x] (* Vladimir Joseph Stephan Orlovsky, Jan 31 2012 *)

a(n)=2^n\/3+1 \\ Charles R Greathouse IV, Jan 31 2012

def A128209(n): return ((1<Chai Wah Wu, Apr 17 2025

a(n) = 1 + 2^n/3 - (-1)^n/3.

G.f.: (1-3*x^2)/(1 - 2*x - x^2 + 2*x^3).

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

cp's OEIS Frontend

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

A135510 Least positive number missing from row n of Stern's diatomic array (see A049456 or A002487).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A178031 Consider the Farey tree A049455/A049456; a(n) = row at which the denominator n first appears (assumes first row is labeled row 1).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions

A178047 Consider the Farey tree A049455/A049456; a(n) = row at which the denominator n first appears (assumes first row is labeled row 0).

Views

Author

Keywords

Comments

Links

Crossrefs

A094968 Indices of Fibonacci numbers in Stern's diatomic series A049456 regarded as a single linear sequence.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A002487 Stern's diatomic series (or Stern-Brocot sequence): a(0) = 0, a(1) = 1; for n > 0: a(2*n) = a(n), a(2*n+1) = a(n) + a(n+1).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Julia

Magma

Maple

Mathematica

PARI

PARI

PARI

Python

Python

Python

Python

R

R

R

Sage

Scheme

Formula

A002487 Stern's diatomic series (or Stern-Brocot sequence): a(0) = 0, a(1) = 1; for n > 0: a(2n) = a(n), a(2n+1) = a(n) + a(n+1).