|
%I M0141 N0056 #612 Mar 22 2024 08:40:08
%S 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,
%T 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,
%U 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
%N 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).
%C Also called fusc(n) [Dijkstra].
%C a(n)/a(n+1) runs through all the reduced nonnegative rationals exactly once [Stern; Calkin and Wilf].
%C If the terms are written as an array:
%C column 0 1 2 3 4 5 6 7 8 9 ...
%C row 0: 0
%C row 1: 1
%C row 2: 1,2
%C row 3: 1,3,2,3
%C row 4: 1,4,3,5,2,5,3,4
%C row 5: 1,5,4,7,3,8,5,7,2,7,5,8,3,7,4,5
%C 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,...
%C ...
%C 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
%C From _N. J. A. Sloane_, Oct 15 2017: (Start)
%C 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.
%C The equations for columns 0,1,2,3,4,... are successively (ignoring row 0):
%C 1 (n >= 1),
%C n (n >= 2),
%C n-1 (n >= 3),
%C 2n-3 (n >= 3),
%C n-2 (n >= 4),
%C 3n-7 (n >= 4),
%C ...
%C and in general column k > 0 is given by
%C A(n,k) = a(k)*n - A156140(k) for n >= ceiling(log_2(k+1))+1, and 0 otherwise.
%C (End)
%C a(n) is the number of odd Stirling numbers S_2(n+1, 2r+1) [Carlitz].
%C 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.
%C a(n+1) = number of alternating bit sets in n [Finch].
%C 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
%C 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].
%C 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].
%C 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
%C 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
%C 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
%C 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
%C Let M be an infinite lower triangular matrix with (1, 1, 1, 0, 0, 0, ...) in every column shifted down twice:
%C 1;
%C 1, 0;
%C 1, 1, 0;
%C 0, 1, 0, 0;
%C 0, 1, 1, 0, 0;
%C 0, 0, 1, 0, 0, 0;
%C 0, 0, 1, 1, 0, 0, 0;
%C ...
%C 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]
%C 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
%C Equals row 1 in an infinite array shown in A178568, sequences of the form
%C a(2*n) = r*a(n), a(2*n+1) = a(n) + a(n+1); r = 1. - _Gary W. Adamson_, May 29 2010
%C 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
%C 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
%C 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
%C 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
%C 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
%C 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
%C 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
%C 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
%C 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
%C 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
%D M. Aigner and G. M. Ziegler, Proofs from THE BOOK, 3rd ed., Berlin, Heidelberg, New York: Springer-Verlag, 2004, p. 97.
%D Elwyn R. Berlekamp, John H. Conway and Richard K. Guy, Winning Ways, Academic Press, NY, 2 vols., 1982, see p. 114.
%D 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.
%D Edsger W. Dijkstra, Selected Writings on Computing, Springer, 1982, p. 232 (sequence is called fusc).
%D 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.
%D Graham Everest, Alf van der Poorten, Igor Shparlinski and Thomas Ward, Recurrence Sequences, Amer. Math. Soc., 2003; see esp. p. 255.
%D Steven R. Finch, Mathematical Constants, Cambridge, 2003, Section 2.16.3; pp. 148-149.
%D Ronald L. Graham, Donald E. Knuth and Oren Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 117.
%D Thomas Koshy, Fibonacci and Lucas numbers with applications, Wiley, 2001, p. 98.
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H T. D. Noe, <a href="/A002487/b002487.txt">Table of n, a(n) for n = 0..10000</a>
%H Boris Adamczewski, <a href="http://dx.doi.org/10.4064/aa142-1-6">Non-converging continued fractions related to the Stern diatomic sequence</a>, Acta Arithm. 142 (1) (2010) 67-78.
%H Jean-Paul Allouche and Michel Mendès France, <a href="http://arxiv.org/abs/1202.0211">Lacunary formal power series and the Stern-Brocot sequence</a>, arXiv preprint arXiv:1202.0211 [math.NT], 2012-2013. - _N. J. A. Sloane_, May 10 2012
%H Jean-Paul Allouche, <a href="http://arxiv.org/abs/1202.4171">On the Stern sequence and its twisted version</a>, arXiv preprint arXiv:1202.4171 [math.NT], 2012.
%H Jean-Paul Allouche, Michel Mendès France, Anna Lubiw, Alfred J. van der Poorten and Jeffrey Shallit, <a href="http://www.math.jussieu.fr/~allouche/bibliorecente.html">Convergents of folded continued fractions</a>.
%H Jean-Paul Allouche and Jeffrey Shallit, <a href="http://dx.doi.org/10.1016/0304-3975(92)90001-V">The ring of k-regular sequences</a>, Theoretical Computer Sci., 98 (1992), 163-197. [<a href="http://www.cs.uwaterloo.ca/~shallit/Papers/as0.ps">Preprint</a>.]
%H Jean-Paul Allouche and Jeffrey Shallit, <a href="http://dx.doi.org/10.1016/S0304-3975(03)00090-2">The ring of k-regular sequences, II</a>, Theoret. Computer Sci., 307 (2003), 3-29. [<a href="http://www.math.jussieu.fr/~allouche/kreg2.ps">Preprint</a>.]
%H Michael Baake and Michael Coons, <a href="https://arxiv.org/abs/1706.00187">A natural probability measure derived from Stern's diatomic sequence</a>, arXiv:1706.00187 [math.NT], 2017.
%H Roland Bacher, <a href="http://arxiv.org/abs/1005.5627">Twisting the Stern sequence</a>, arXiv:1005.5627 [math.CO], 2010.
%H Bruce Bates, Martin Bunder and Keith Tognetti, <a href="https://doi.org/10.1016/j.ejc.2010.04.002">Linking the Calkin-Wilf and Stern-Brocot trees</a>, Eur. J. Comb., Vol. 31, No. 7 (2010), pp. 1637-1661.
%H Bruce Bates and Toufik Mansour, <a href="http://dx.doi.org/10.1016/j.jcta.2010.09.002">The q-Calkin-Wilf tree</a>, Journal of Combinatorial Theory Series A, Vol. 118, No. 3 (2011), pp. 1143-1151.
%H Marjorie Bicknell-Johnson, <a href="http://www.fq.math.ca/Scanned/41-2/bicknell.pdf">Stern's Diatomic Array Applied to Fibonacci Representations</a>, Fibonacci Quarterly, Vol. 41 (2003), pp. 169-180.
%H Arie Bos, <a href="/A002487/a002487_3.pdf">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</a>.
%H Richard P. Brent, Michael Coons and Wadim Zudilin, <a href="http://maths-people.anu.edu.au/~brent/pd/Brent_AustMS14.pdf">Asymptotics of a Mahler Function</a>, Slides of talk presented at AustMS/NZMS 2014, Melbourne, 8 December 2014.
%H Neil Calkin and Herbert S. Wilf, <a href="http://www.math.upenn.edu/~wilf/website/recounting.pdf">Recounting the rationals</a>, Amer. Math. Monthly, Vol. 107, No. 4 (2000), pp. 360-363.
%H L. Carlitz, <a href="http://projecteuclid.org/euclid.bams/1183525946">A problem in partitions related to the Stirling numbers</a>, Bull. Amer. Math. Soc., Vol. 70, No. 2 (1964), pp. 275-278. [<a href="/A002487/a002487abs1.html">Abstract</a>.]
%H L. Carlitz, <a href="http://rivista.math.unipr.it/fulltext/1964-5/1964-5-061.pdf">A problem in partitions related to the Stirling numbers</a>, Riv. Mat. Univ. Parma, (2) 5 (1964), 61-75.
%H Michael Coons, <a href="https://doi.org/10.1142/S1793042110002958">The transcendence of series related to Stern's diatomic sequence</a>, International Journal of Number Theory 6.01 (2010): 211-217.
%H Michael Coons, <a href="https://www.emis.de/journals/INTEGERS/papers/l35/l35.Abstract.html">On some conjectures concerning Stern's sequence and its twist</a>, Integers 11.6 (2011): 775-789.
%H Michael Coons, <a href="https://www.emis.de/journals/INTEGERS/papers/m3/m3.Abstract.html">A Correlation Identity for Stern's Sequence</a>, Integers 12.3 (2012): 459-464.
%H Michael Coons and Jeffrey Shallit, <a href="http://dx.doi.org/10.1016/j.disc.2011.07.029">A pattern sequence approach to Stern's sequence</a>, Discrete Math., Vol. 311 (2011), pp. 2630-2633.
%H Michael Coons and Jason Tyler, <a href="http://arxiv.org/abs/1307.1521">The maximal order of Stern's diatomic sequence</a>, arXiv:1307.1521 [math.NT], 2013-2014.
%H Kevin M. Courtright and James A. Sellers, <a href="http://www.emis.de/journals/INTEGERS/papers/e6/e6.Abstract.html">Arithmetic Properties for Hyper m-ary Partitions</a>, INTEGERS, Vol. 4 (2004), Article A6.
%H Valerio De Angelis, <a href="http://www.jstor.org/stable/10.4169/amer.math.monthly.124.5.451">The Stern diatomic sequence via generalized Chebyshev polynomials</a>, American Mathematical Monthly 124.5 (2017): 451-455. See <a href="https://arxiv.org/abs/1511.02422">also</a>, arXiv:1511.02422 [math.NT], 2015.
%H Philip de Castro et al., <a href="https://doi.org/10.1080/00029890.2018.1449523">Counting binomial coefficients divisible by a prime power</a>, Amer. Math. Monthly, Vol. 125, No. 6 (2018), pp. 531-540. See Table p. 534.
%H Colin Defant, <a href="https://doi.org/10.37236/5342">Upper Bounds for Stern's Diatomic Sequence and Related Sequences</a>, Electronic Journal of Combinatorics, Vol. 23, No. 4 (2016), #P4.8.
%H Georges De Rham, <a href="http://dx.doi.org/10.5169/seals-12823">Un peu de mathématiques à propos d'une courbe plane</a>, Elemente der Math., Vol. 2 (1947), pp. 73-76 and 89-97.
%H Marc Deléglise, Paul Erdős and Jean-Louis Nicolas, <a href="http://dx.doi.org/10.1016/S0012-365X(98)00330-6">Sur les ensembles représentés par les partitions d'un entier n</a> [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
%H Edsger W. Dijkstra, <a href="http://www.cs.utexas.edu/users/EWD/ewd05xx/EWD570.PDF">An exercise for Dr. R. M. Burstall</a>.
%H Edsger W. Dijkstra, <a href="http://www.cs.utexas.edu/users/EWD/ewd05xx/EWD578.PDF">More about the function "fusc"</a>.
%H Karl Dilcher and Larry Ericksen, <a href="https://doi.org/10.37236/4822">Hyperbinary expansions and Stern polynomials</a>, Elec. J. Combin, Vol. 22 (2015), #P2.24.
%H Karl Dilcher and Larry Ericksen, <a href="https://www.emis.de/journals/INTEGERS/papers/p50/p50.Abstract.html">Factors and irreducibility of generalized Stern polynomials</a>, Integers, Vol. 15 (2015), #A50.
%H Karl Dilcher and Larry Ericksen, <a href="https://dx.doi.org/10.1007%2Fs11139-016-9864-3">Continued fractions and Stern polynomials</a>, Ramanujan Journal, Vol. 45 (2017), pp. 659-681.
%H Karl Dilcher and Larry Ericksen, <a href="https://www.emis.de/journals/JIS/VOL21/Dilcher/dilcher7.html">Polynomials Characterizing Hyper b-ary Representations</a>, J. Int. Seq., Vol. 21 (2018), Article 18.4.3.
%H Karl Dilcher and Larry Ericksen, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL22/Dilcher/dilcher44.html">Polynomial Analogues of Restricted b-ary Partition Functions</a>, J. Int. Seq., Vol. 22 (2019), Article 19.3.2.
%H Tom Edgar, <a href="http://math.colgate.edu/~integers/s47/s47.Abstract.html">On the number of hyper m-ary partitions</a>, Integers, Vol. 18 (2018), Article #A47.
%H De-Jun Feng, Pierre Liardet and Alain Thomas, <a href="http://www.math.cuhk.edu.hk/~djfeng/fengpapers/Feng-Liardet-Thomsa/FengLiardetThomasPartition3R.pdf">Partition functions in numeration systems with bounded multiplicity, Uniform Distribution Theory</a>, Vol. 9, No. 1 (2014).
%H Steven R. Finch, P. Sebah and Z.-Q. Bai, <a href="http://arXiv.org/abs/0802.2654">Odd Entries in Pascal's Trinomial Triangle</a>, arXiv:0802.2654 [math.NT], 2008.
%H Aviezri S. Fraenkel, <a href="http://www.wisdom.weizmann.ac.il/~fraenkel/Papers/RationalGames3.pdf">Ratwyt</a>, Dec 28 2011.
%H Thomas Garrity, <a href="http://arxiv.org/abs/1206.6685">A multi-dimensional continued fraction generalization of Stern's diatomic sequence</a>, arXiv:1206.6685 [math.CO], 2012-2013.
%H Thomas Garrity, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL16/Garrity/garrity4.html">A multi-dimensional continued fraction generalization of Stern's diatomic sequence</a>, Journal of Integer Sequences, Vol. 16 (2013), #13.7.7.
%H Michael Gilleland, <a href="/selfsimilar.html">Some Self-Similar Integer Sequences</a>.
%H Jose Grimm, <a href="https://jfr.unibo.it/article/view/4771">Implementation of Bourbaki's Elements of Mathematics in Coq: Part Two, From Natural Numbers to Real Numbers</a>, Journal of Formalized Reasoning, Vol. 9, No. 2 (2016), pp. 1-52; see p. 38.
%H Brian Hayes, <a href="https://www.jstor.org/stable/27858048">On the Teeth of Wheels</a>, American Scientist, Vol. 88, No. 4 (July-August 2000), pp. 296-300 (5 pages).
%H Andreas M. Hinz, Sandi Klavžar, Uroš Milutinović and Ciril Petr,, <a href="http://dx.doi.org/10.1007/978-3-0348-0237-6">The Tower of Hanoi - Myths and Maths</a>, Birkhäuser 2013. See page 115. <a href="http://tohbook.info">Book's website</a>
%H Andreas M. Hinz, Sandi Klavžar, Uroš Milutinović, Daniele Parisse and Ciril Petr, <a href="http://dx.doi.org/10.1016/j.ejc.2004.04.009">Metric properties of the Tower of Hanoi graphs and Stern's diatomic sequence</a> European J. Combin., Vol. 26, No. 5 (2005), pp. 693-708.
%H Johannes Kepler, <a href="https://archive.org/stream/ioanniskepplerih00kepl#page/27/mode/1up">Harmonices Mundi, Vol. III (1619) p.27</a>.
%H Donald E. Knuth, C. P. Rupert, Alex Smith and Richard Stong, <a href="http://www.jstor.org/stable/3647762">Recounting the Rationals, Continued: 10906</a>, solution by Moshe Newman, American Mathematical Monthly, Vol. 110, No. 7 (2003), pp. 642-643.
%H Jennifer Lansing, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL16/Lansing/lansing3.html">Distribution of Values of the Binomial Coefficients and the Stern Sequence</a>, Journal of Integer Sequences, Vol. 16 (2013), Article 13.3.7.
%H Jennifer Lansing, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL17/Lansing/lansing2.html">Largest Values for the Stern Sequence</a>, Journal of Integer Sequences, Vol. 17 (2014), Article 14.7.5.
%H D. H. Lehmer, <a href="http://www.jstor.org/stable/2299356">On Stern's Diatomic Series</a>, Amer. Math. Monthly, Vol. 36, No. 1 (1929), pp. 59-67. [<a href="/A002487/a002487_1.pdf">Annotated and corrected scanned copy</a>.]
%H Julien Leroy, Michel Rigo and Manon Stipulanti, <a href="http://dx.doi.org/10.1016/j.disc.2017.01.003">Counting the number of non-zero coefficients in rows of generalized Pascal triangles</a>, Discrete Mathematics, Vol. 340 (2017), pp. 862-881. Also available at <a href="http://hdl.handle.net/2268/205077">Université de Liège</a>.
%H Peter Luschny, <a href="http://www.oeis.org/wiki/User:Peter_Luschny/SternsDiatomic">Rational Trees and Binary Partitions</a>.
%H Alan J. Macfarlane, <a href="https://doi.org/10.1088/0305-4470/37/45/006">Linear reversible second-order cellular automata and their first-order matrix equivalents</a>, Journal of Physics A: Mathematical and General 37.45 (2004): 10791. See Fig. 2.
%H Laura Monroe, <a href="https://arxiv.org/abs/2103.05810">Binary Signed-Digit Integers, the Stern Diatomic Sequence and Stern Polynomials</a>, arXiv:2103.05810 [math.NT], 2021.
%H Sam Northshield, <a href="http://dx.doi.org/10.4169/000298910X496714">Stern's diatomic sequence 0, 1, 1, 2, 1, 3, 2, 3, 1, 4, ...</a>, Amer. Math. Monthly, Vol. 117, No. 7 (2010), pp. 581-598.
%H Sam Northshield, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Northshield/north4.html">An Analogue of Stern's Sequence for Z[sqrt(2)]</a>, Journal of Integer Sequences, Vol. 18 (2015), Article 15.11.6.
%H Sam Northshield, <a href="https://arxiv.org/abs/1905.10369">Re^3counting the Rationals</a>, arXiv:1905.10369 [math.NT], 2019.
%H Project Euler, <a href="https://projecteuler.net/problem=169">Problem 169 - Exploring the number of different ways a number can be expressed as a sum of powers of 2</a>.
%H Bruce Reznick, <a href="http://dx.doi.org/10.1007/978-1-4612-3464-7_29">Some binary partition functions</a>, 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.
%H Bruce Reznick, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL11/Reznick/reznick4.html">Regularity properties of the Stern enumeration of the Rationals</a>, Journal of Integer Sequences, Vol. 11 (2008) Article 08.4.1.
%H Jürgen W. Sander, Jörn Steuding and Rasa Steuding, <a href="https://doi.org/10.4171/EM/170">Diophantine aspects of the Calkin-Wilf iteration</a>, El. Math., Vol. 66, No. 2 (2011) pp. 45-55. doi:10.4171/EM/170.
%H Rémy Sigrist, <a href="https://arxiv.org/abs/2301.06039">Nonperiodic tilings related to Stern's diatomic series and based on tiles decorated with elements of F_p</a>, arXiv:2301.06039 [math.CO], 2023.
%H N. J. A. Sloane, <a href="/stern_brocot.html">Stern-Brocot or Farey Tree</a>.
%H N. J. A. Sloane and Brady Haran, <a href="https://www.youtube.com/watch?v=j0o-pMIR8uk">Amazing Graphs III</a>, Numberphile video (2019).
%H Richard P. Stanley and Herbert S. Wilf, <a href="http://www-math.mit.edu/~rstan/papers/stern.pdf">Refining the Stern Diatomic Sequence</a>, unpublished.
%H Richard P. Stanley and Herbert S. Wilf, <a href="/A002487/a002487.pdf">Refining the Stern Diatomic Sequence</a> [Cached copy, with permission]
%H Jörn Steuding, Stefanie Hofmann and Gertraud Schuster, <a href="https://ems.press/content/serial-article-files/1809">Euclid, Calkin & Wilf - playing with rationals</a>, Elemente der Mathematik, Vol. 63, No. 3 (2008), pp. 109-117.
%H Ralf Stephan, <a href="https://arxiv.org/abs/math/0307027">Divide-and-conquer generating functions. I. Elementary sequences</a>, arXiv:math/0307027 [math.CO], 2003.
%H M. A. Stern, <a href="http://dx.doi.org/10.1515/crll.1858.55.193">Über eine zahlentheoretische Funktion</a>, J. Reine Angew. Math., Vol. 55 (1858), pp. 193-220.
%H Maciej Ulas, <a href="http://arxiv.org/abs/1102.5111">Arithmetic properties of the sequence of degrees of Stern polynomials and related results</a>, arXiv:1102.5111 [math.CO], 2011.
%H Maciej Ulas and Oliwia Ulas, <a href="http://arxiv.org/abs/1102.5109">On certain arithmetic properties of Stern polynomials</a>, arXiv:1102.5109 [math.CO], 2011.
%H Igor Urbiha, <a href="http://hrcak.srce.hr/file/1591">Some properties of a function studied by De Rham, Carlitz and Dijkstra and its relation to the (Eisenstein -) Stern's diatomic sequence</a>, Math. Commun., Vol. 6 (2002), pp. 181-198.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Calkin-WilfTree.html">Calkin-Wilf Tree</a> and <a href="http://mathworld.wolfram.com/SternsDiatomicSeries.html">Stern's Diatomic Series</a>.
%H Yasuhisa Yamada, <a href="https://arxiv.org/abs/2004.00278">A function from Stern's diatomic sequence, and its properties</a>, arXiv:2004.00278 [math.NT], 2020.
%H <a href="/index/Cor#core">Index entries for "core" sequences</a>
%H <a href="/index/Fo#fraction_trees">Index entries for fraction trees</a>
%H <a href="/index/Ra#rational">Index entries for sequences related to enumerating the rationals</a>
%H <a href="/index/St#Stern">Index entries for sequences related to Stern's sequences</a>
%H <a href="/index/Tra#trees">Index entries for sequences related to trees</a>
%F 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
%F 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
%F 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
%F a(n) = Sum_{k=0..floor((n-1)/2)} (binomial(n-k-1, k) mod 2). - _Paul Barry_, Sep 13 2004
%F a(n) = Sum_{k=0..n-1} (binomial(k, n-k-1) mod 2). - _Paul Barry_, Mar 26 2005
%F 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
%F 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
%F G.f.: x * Product_{k>=0} (1 + x^(2^k) + x^(2^(k+1))) [Carlitz].
%F a(n) = a(n-2) + a(n-1) - 2*(a(n-2) mod a(n-1)). - _Mike Stay_, Nov 06 2006
%F A079978(n) = (1 + e^(i*Pi*A002487(n)))/2, i=sqrt(-1). - _Paul Barry_, Jan 14 2005
%F 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
%F 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
%F 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
%F a(2^n + k) = a(2^n - k) + a(k) (0 <= k <= 2^n). - Arie Werksma (werksma(AT)tiscali.nl), Apr 18 2008
%F 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
%F 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
%F 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
%F a(n) = A126606(n + 1) / 2. - _Reikku Kulon_, Oct 05 2008
%F 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
%F 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
%F a(2*n-1) = A007306(n), n > 0. - _Yosu Yurramendi_, Jun 23 2014
%F a(n*2^m) = a(n), m>0, n > 0. - _Yosu Yurramendi_, Jul 03 2014
%F 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
%F 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
%F 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
%F 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
%F From _Yosu Yurramendi_, Jul 13 2016: (Start)
%F Let n be a natural number and [b_m b_(m-1) ... b_1 b_0] its binary expansion with b_m=1.
%F Let L = Sum_{i=0..m} b_i be the number of binary digits equal to 1 (L >= 1).
%F 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.
%F 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.
%F 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.
%F Then a(n) = f(L+1) (see example). (End)
%F a(n) = A001222(A260443(n)) = A000120(A277020(n)). Also a(n) = A000120(A101624(n-1)) for n >= 1. - _Antti Karttunen_, Nov 05 2016
%F (a(n-1) + a(n+1))/a(n) = A037227(n) for n >= 1. - _Peter Bala_, Feb 07 2017
%F 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
%F From _I. V. Serov_, Jun 14 2017: (Start)
%F a(n) = A287896(n-1) - 1*A288002(n-1) for n > 1;
%F a(n) = A007306(n-1) - 2*A288002(n-1) for n > 1. (End)
%F From _Yosu Yurramendi_, Feb 14 2018: (Start)
%F a(2^(m+2) + 2^(m+1) + k) - a(2^(m+1) + 2^m + k) = 2*a(k), m >= 0, 0 <= k < 2^m.
%F a(2^(m+2) + 2^(m+1) + k) - a(2^(m+1) + k) = a(2^m + k), m >= 0, 0 <= k < 2^m.
%F 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.
%F (End)
%F From _Yosu Yurramendi_, May 08 2018: (Start)
%F a(2^m) = 1, m >= 0.
%F 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.
%F (End)
%e Stern's diatomic array begins:
%e 1,1,
%e 1,2,1,
%e 1,3,2,3,1,
%e 1,4,3,5,2,5,3,4,1,
%e 1,5,4,7,3,8,5,7,2,7,5,8,3,7,4,5,1,
%e 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,...
%e ...
%e 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
%e From _I. V. Serov_, Jun 01 2017: (Start)
%e a(n) is the length of the Christoffel word chf(n):
%e n chf(n) A070939(n) a(n)
%e 1 '-' 1 1
%e 2 '+' 2 1
%e 3 '+-' 2 2
%e 4 '-' 3 1
%e 5 '--+' 3 3
%e 6 '-+' 3 2
%e ... (End)
%e 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
%p 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);
%p 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.
%p 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:
%p 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
%p # next Maple program:
%p a:= proc(n) option remember; `if`(n<2, n,
%p (q-> a(q)+(n-2*q)*a(n-q))(iquo(n, 2)))
%p end:
%p seq(a(n), n=0..100); # _Alois P. Heinz_, Feb 11 2021
%p fusc := proc(n) local a, b, c; a := 1; b := 0;
%p for c in convert(n, base, 2) do
%p if c = 0 then a := a + b else b := a + b fi od;
%p b end:
%p seq(fusc(n), n = 0..91); # _Peter Luschny_, Nov 09 2022
%t 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 *)
%t Onemore[l_] := Transpose[{l, l + RotateLeft[l]}] // Flatten;
%t NestList[Onemore, {1}, 5] // Flatten (*gives [a(1), ...]*) (* Takashi Tokita, Mar 09 2003 *)
%t ToBi[l_] := Table[2^(n - 1), {n, Length[l]}].Reverse[l]; Map[Length,
%t Split[Sort[Map[ToBi, Table[IntegerDigits[n - 1, 3], {n, 500}]]]]] (*give [a(1), ...]*) (* Takashi Tokita, Mar 10 2003 *)
%t 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 *)
%t a[0] = 0; a[1] = 1;
%t 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 *)
%t 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 *)
%o (PARI) {a(n) = n=abs(n); if( n<2, n>0, a(n\2) + if( n%2, a(n\2 + 1)))};
%o (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
%o (PARI) 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
%o (Haskell)
%o a002487 n = a002487_list !! n
%o a002487_list = 0 : 1 : stern [1] where
%o stern fuscs = fuscs' ++ stern fuscs' where
%o fuscs' = interleave fuscs $ zipWith (+) fuscs $ (tail fuscs) ++ [1]
%o interleave [] ys = ys
%o interleave (x:xs) ys = x : interleave ys xs
%o -- _Reinhard Zumkeller_, Aug 23 2011
%o (R)
%o N <- 50 # arbitrary
%o a <- 1
%o for (n in 1:N)
%o {
%o a[2*n ] = a[n]
%o a[2*n + 1] = a[n] + a[n+1]
%o a
%o }
%o a
%o # _Yosu Yurramendi_, Oct 04 2014
%o (Scheme)
%o ;; An implementation of memoization-macro definec can be found for example in: http://oeis.org/wiki/Memoization
%o (definec (A002487 n) (cond ((<= n 1) n) ((even? n) (A002487 (/ n 2))) (else (+ (A002487 (/ (- n 1) 2)) (A002487 (/ (+ n 1) 2))))))
%o ;; _Antti Karttunen_, Nov 05 2016
%o (Python)
%o from functools import lru_cache
%o @lru_cache(maxsize=None)
%o 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
%o (Python)
%o def a(n):
%o a, b = 1, 0
%o while n > 0:
%o if n & 1:
%o b += a
%o else:
%o a += b
%o n >>= 1
%o return b
%o # _Reza K Ghazi_, Dec 29 2021
%o (Sage)
%o def A002487(n):
%o M = [1, 0]
%o for b in n.bits():
%o M[b] = M[0] + M[1]
%o return M[1]
%o print([A002487(n) for n in (0..91)])
%o # For a dual see A174980. _Peter Luschny_, Nov 28 2017
%o (Julia)
%o using Nemo
%o function A002487List(len)
%o a, A = QQ(0), [0,1]
%o for n in 1:len
%o a = next_calkin_wilf(a)
%o push!(A, denominator(a))
%o end
%o A end
%o A002487List(91) |> println # _Peter Luschny_, Mar 13 2018
%o (R) # Given n, compute a(n) by taking into account the binary representation of n
%o a <- function(n){
%o b <- as.numeric(intToBits(n))
%o l <- sum(b)
%o m <- which(b == 1)-1
%o d <- 1
%o if(l > 1) for(j in 1:(l-1)) d[j] <- m[j+1]-m[j]+1
%o f <- c(0,1)
%o if(l > 1) for(j in 3:(l+1)) f[j] <- d[j-2]*f[j-1]-f[j-2]
%o return(f[l+1])
%o } # _Yosu Yurramendi_, Dec 13 2016
%o (R) # computes the sequence as a vector A, rather than function a() as above.
%o A <- c(1,1)
%o maxlevel <- 5 # by choice
%o for(m in 1:maxlevel) {
%o A[2^(m+1)] <- 1
%o for(k in 1:(2^m-1)) {
%o r <- m - floor(log2(k)) - 1
%o A[2^r*(2*k+1)] <- A[2^r*(2*k)] + A[2^r*(2*k+2)]
%o }}
%o A # _Yosu Yurramendi_, May 08 2018
%o (Magma) [&+[(Binomial(k, n-k-1) mod 2): k in [0..n]]: n in [0..100]]; // _Vincenzo Librandi_, Jun 18 2019
%o (Python)
%o def A002487(n): return sum(int(not (n-k-1) & ~k) for k in range(n)) # _Chai Wah Wu_, Jun 19 2022
%Y Cf. A000123, A000360, A001045, A002083, A011655, A020950, A026741, A037227, A046815, A070871, A070872, A071883, A073459, A084091, A101624, A126606, A174980, A174981, A178239, A178568, A212288, A213369, A260443, A277020, A277325, A287729, A287730, A293160.
%Y Record values are in A212289.
%Y If the 1's are replaced by pairs of 1's we obtain A049456.
%Y Inverse: A020946.
%Y Cf. a(A001045(n)) = A000045(n). a(A062092(n)) = A000032(n+1).
%Y Cf. A064881-A064886 (Stern-Brocot subtrees).
%Y A column of A072170.
%Y Cf. A049455 for the 0,1 version of Stern's diatomic array.
%Y Cf. A000119, A262097 for analogous sequences in other bases and A277189, A277315, A277328 for related sequences with similar graphs.
%Y Cf. A086592 and references therein to other sequences related to Kepler's tree of fractions.
%K nonn,easy,nice,core,look
%O 0,4
%A _N. J. A. Sloane_
%E Additional references and comments from _Len Smiley_, _Joshua Zucker_, _Rick L. Shepherd_ and Herbert S. Wilf
%E Typo in definition corrected by _Reinhard Zumkeller_, Aug 23 2011
%E Incorrect formula deleted and text edited by _Johannes W. Meijer_, Feb 07 2013
|
