|
| |
|
|
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).
(Formerly M0141 N0056)
|
|
120
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,4
|
|
|
COMMENTS
|
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:
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
then the sum of the k-th row is 3^(k-1), each columns 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
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 (see 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) = 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) = partitions of the n-th integer expressible as the sum of distinct even-subscripted Fibonacci numbers (= A054204(n)), into sums of distinct Fibonacci numbers numbers [Bicknell-Johnson].
a(n+1) = number of odd binomial(n-k,k), 0 <= 2*k < n. [Carlitz].
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 GF 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
Contribution from Gary W. Adamson, Dec 11 2009: (Start)
Let M = 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;
...
A002487 = Lim_{n->inf.} M^n, a left-shifted vector considered as a sequence. (Cf. A026741) (End)
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-Sierpinski 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, July 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
|
|
|
REFERENCES
|
M. Aigner and G. M. Ziegler, Proofs from THE BOOK, 3rd ed., Berlin, Heidelberg, New York: Springer-Verlag, 2004, p. 97.
J.-P. Allouche and M. Mendes France, Stern-Brocot polynomials and power series, Arxiv preprint arXiv:1202.0211, 2012. - N. J. A. Sloane, May 10 2012
J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197.
J.-P. Allouche and J. Shallit, The ring of k-regular sequences, II, Theoret. Computer Sci., 307 (2003), 3-29.
Roland Bacher, Twisting the Stern sequence, arXiv:1005.5627.
B. Bates and T. Mansour, The q-Calkin-Wilf tree, Journal of Combinatorial Theory Series A, Volume 118 Issue 3, 2011.
E. R. Berlekamp, J. H. Conway and R. K. Guy, Winning Ways, Academic Press, NY, 2 vols., 1982, see p. 114.
M. Bicknell-Johnson, Stern's Diatomic Array Applied to Fibonacci Representations," Fibonacci Quarterly 41 (2003), pp. 169-180.
N. Calkin and H. S. Wilf, Recounting the rationals, Amer. Math. Monthly, 107 (No. 4, 2000), pp. 360-363.
L. Carlitz, A problem in partitions related to the Stirling numbers, Bull. Amer. Math. Soc., 70(2) (1964), pp. 275-278.
L. Carlitz, A problem in partitions related to the Stirling numbers, Riv. Mat. Univ. Parma, (2) 5 (1964), 61-75.
M. Coons and J. Shallit, A pattern sequence approach to Stern's sequence, Discrete Math., 311 (2011), 2630-2633.
Courtright, K. M. and Sellers, J. A., Arithmetic Properties for Hyper m-ary Partitions, INTEGERS 4 (2004), Article A6
G. De Rham, Un peu de mathematiques a propos d'une courbe plane, Elemente der Math. 2 (1947), pp. 73-76 and 89-97.
Deleglise, Marc; Erdos, Paul; Nicolas, Jean-Louis. Sur les ensembles representes par les partitions d'un entier n. [Sets represented by partitions of an integer n] Paul Erdos memorial collection. Discrete Math. 200 (1999), no. 1-3, 27--48. MR1692277 (2000e:05012). See Table 1. N. J. A. Sloane, Mar 18 2012
E. 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) 36-42, Feb 18, 1850. Werke, II, pp. 705-711.
G. Everest, A. van der Poorten, I. Shparlinski and T. Ward, Recurrence Sequences, Amer. Math. Soc., 2003; see esp. p. 255.
S. R. Finch, Mathematical Constants, Cambridge, 2003, Section 2.16.3; pp. 148-149.
R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 117.
A. M. Hinz, S. Klavzar, U. Milutinovic, D. Parisse, and C. Petr, Metric properties of the Tower of Hanoi graphs and Stern's diatomic sequence. European J. Combin. 26 (2005), no. 5, 693-708.
T. Koshy, Fibonacci and Lucas numbers with applications, Wiley, 2001, p. 98.
D. E. Knuth, Problem 10906, American Mathematical Monthly; solution by Moshe Newman, American Mathematical Monthly, 110 (No. 7, 2003), 642-643.
D. H. Lehmer, On Stern's Diatomic Series, Amer. Math. Monthly 36(1) 1929, pp. 59-67.
Sam Northshield, "Stern's Diatomic Sequence 0,1,1,2,1,3,2,3,1,4,...", Amer. Math. Month., Vol. 117 (7), pp. 581-598, 2010.
B. Reznick, Some binary partition functions, in "Analytic number theory" (Conf. in honor P. T. Bateman, Allerton Park, IL, 1989), 451-477, Progr. Math., 85, Birkhaeuser Boston, Boston, MA, 1990.
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).
R. P. Stanley and H. S. Wilf, Refining the Stern Diatomic Sequence.
M. A. Stern, Ueber eine zahlentheoretische Funktion, J. Reine Angew. Math., 55 (1858), 193-220.
I. 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. 6 (2002) 181-198.
|
|
|
LINKS
|
T. D. Noe, Table of n, a(n) for n = 0..10000
Jean-Paul Allouche, On the Stern sequence and its twisted version, Arxiv preprint arXiv:1202.4171, 2012
J.-P. Allouche, M. Mendes France, A. Lubiw, A.J. van der Poorten and J. Shallit, Convergents of folded continued fractions
J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197.
J.-P. Allouche and J. Shallit, The Ring of k-regular Sequences, II
L. Carlitz, A problem in partitions related to the Stirling numbers (abstract)
E. W. Dijkstra, An exercise for Dr. R. M. Burstall
E. W. Dijkstra, More about the function ``fusc''
S. R. Finch, P. Sebah and Z.-Q. Bai, Odd Entries in Pascal's Trinomial Triangle (arXiv:0802.2654)
A. S. Fraenkel, Ratwyt, December 28 2011.
Michael Gilleland, Some Self-Similar Integer Sequences
B. Hayes, On the Teeth of Wheels
A. M. Hinz, S. Klavžar, U. Milutinović, C. Petr, The Tower of Hanoi - Myths and Maths, Birkhäuser 2013. See page 115. Book's website
Peter Luschny, Rational Trees and Binary Partitions. [Peter Luschny, Jun 15 2010]
Mathematical Problems, Problem number 169 - Knut Angstrom (angstrom.knut(AT)telia.com), May 05 2009
N. J. A. Sloane, Stern-Brocot or Farey Tree
R. Stephan, Divide-and-conquer generating functions. I. Elementary sequences
Maciej Ulas, Arithmetic properties of the sequence of degrees of Stern polynomials and related results (arXiv:1102.5111)
Maciej Ulas and Oliwia Ulas, On certain arithmetic properties of Stern polynomials (arXiv:1102.5109)
Eric Weisstein's World of Mathematics, Stern's Diatomic Series
Eric Weisstein's World of Mathematics, Calkin-Wilf Tree
H. S. Wilf, Recounting the Rationals (with N. Calkin)
Index entries for sequences related to Stern's sequences
Index entries for "core" sequences
Index entries for sequences related to trees
|
|
|
FORMULA
|
a(0) = 0; a(1) = 1; a(2*k) = a(k); a(2*k+1) = a(k) + a(k+1) generates the same sequence with an initial 0 - David W. Wilson
a(n+1) = (2*k+1)*a(n) - a(n-1) where k = [a(n-1) / a(n) ] is the largest integer smaller than or equal to 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
a(n) = sum{k=0..floor((n-1)/2), mod(binomial(n-k-1, k), 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 * prod(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)) where x mod y gives the remainder after dividing x by y - 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->00) 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 by 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
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
|
|
|
MAPLE
|
A002487 := proc(n) option remember; if n <= 1 then n elif n mod 2 = 0 then A002487(n/2); else A002487((n-1)/2)+A002487((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]
|
|
|
MATHEMATICA
|
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}]
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
|
|
|
PROG
|
(PARI) a(n)=if(n<2, n>0, a(n\2)+if(n%2, a(n\2+1)))
(PARI) 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]
(Haskell)
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
|
|
|
CROSSREFS
|
Cf. A084091, A020950, A046815, A070871, A070872, A071883, A001045, A002083, A073459, A000123, A126606, A049455, A011655, A026741, A178239, A178568, A174980, A174981, A213369, A212288.
Record values are in A212289.
If the 1's are replaced by pairs of 1's we obtain A049456.
Inverse: A020946.
Cf. A002487(A001045(n)) = A000045(n). A002487(A062092(n)) = A000032(n+1).
Cf. A064881-A064886 (Stern-Brocot subtrees). A column of A072170.
Sequence in context: A071912 A070940 A020651 * A060162 A026730 A075256
Adjacent sequences: A002484 A002485 A002486 * A002488 A002489 A002490
|
|
|
KEYWORD
|
nonn,easy,nice,core
|
|
|
AUTHOR
|
N. J. A. Sloane.
|
|
|
EXTENSIONS
|
Additional references and comments from Leonard Smiley (smiley(AT)math.uaa.alaska.edu), Joshua Zucker, Rick L. Shepherd and Herb Wilf (wilf(AT)math.upenn.edu).
More terms from Arie Werksma (Werksma(AT)Tiscali.nl), Jul 11 2008
Formula corrected by Mats Granvik, Oct 10 2009
Typo in definition fixed by Reinhard Zumkeller, Aug 23 2011
Incorrect formula deleted and text edited by Johannes W. Meijer, Feb 07 2013
|
|
|
STATUS
|
approved
|
| |
|
|
