login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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)
231
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:

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

Comment 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) = 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) = 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], 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 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

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;

   ...

   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

REFERENCES

M. Aigner and G. M. Ziegler, Proofs from THE BOOK, 3rd ed., Berlin, Heidelberg, New York: Springer-Verlag, 2004, p. 97.

E. R. Berlekamp, J. H. Conway and R. K. Guy, Winning Ways, Academic Press, NY, 2 vols., 1982, see p. 114.

L. Carlitz, A problem in partitions related to the Stirling numbers, Riv. Mat. Univ. Parma, (2) 5 (1964), 61-75.

Krishna Dasaratha, Laure Flapan, Chansoo Lee, Cornelia Mihaila, Nicholas Neumann-Chun, Sarah Peluse, Matthew Stroegeny, A family of multi-dimensional continued fraction Stern sequences, Abtracts Amer. Math. Soc., 33 (#1, 2012), #1077-05-2543.

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.

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

LINKS

T. D. Noe, Table of n, a(n) for n = 0..10000

B. Adamczewski, Non-converging continued fractions related to the Stern diatomic sequence, Acta Arithm. 142 (1) (2010) 67-78.

J.-P. Allouche and M. Mendes 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.

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. [Preprint.]

J.-P. Allouche and J. Shallit, The ring of k-regular sequences, II, Theoret. Computer Sci., 307 (2003), 3-29. [Preprint.]

Roland Bacher, Twisting the Stern sequence, arXiv:1005.5627 [math.CO], 2010.

B. Bates and T. Mansour, The q-Calkin-Wilf tree, Journal of Combinatorial Theory Series A, Volume 118 Issue 3, 2011.

M. Bicknell-Johnson, Stern's Diatomic Array Applied to Fibonacci Representations, Fibonacci Quarterly 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.

R. P. Brent, M. Coons, W. Zudilin, Asymptotics of a Mahler Function, Slides of talk presented at AustMS/NZMS 2014, Melbourne, 8 December 2014.

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. [Abstract.]

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.

M. Coons and J. Shallit, A pattern sequence approach to Stern's sequence, Discrete Math., 311 (2011), 2630-2633.

Michael Coons and Jason Tyler, The maximal order of Stern’s diatomic sequence, arXiv:1307.1521 [math.NT], 2013-2014.

K. M. Courtright, and J. A. Sellers, Arithmetic Properties for Hyper m-ary Partitions, INTEGERS 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.

Colin Defant, Upper Bounds for Stern’s Diatomic Sequence and Related Sequences, Electronic Journal of Combinatorics 23(4) (2016), #P4.8.

G. De Rham, Un peu de mathématiques à propos d'une courbe plane, Elemente der Math. 2 (1947), pp. 73-76 and 89-97.

Marc Deleglise, Paul Erdős, Jean-Louis Nicolas, Sur les ensembles representes par les partitions d'un entier n [Sets represented by partitions of an integer n] Paul Erdős 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. W. Dijkstra, An exercise for Dr. R. M. Burstall

E. W. Dijkstra, More about the function ``fusc''

K. Dilcher and L. Ericksen, Hyperbinary expansions and Stern polynomials, Elec. J. Combin, 22, 2015, #P2.24.

K. Dilcher, L. Ericksen, Factors and irreducibility of generalized Stern polynomials, Integers, #A50 15 (2015).

Karl Dilcher and Larry Ericksen, Continued fractions and Stern polynomials. Ramanujan Journal (2017).

D.-J. Feng, P. Liardet and A. Thomas, Partition functions in numeration systems with bounded multiplicity, Uniform Distribution Theory, submitted 2013.

S. R. Finch, P. Sebah and Z.-Q. Bai, Odd Entries in Pascal's Trinomial Triangle, arXiv:0802.2654 [math.NT], 2008.

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

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

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.

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, 110 (No. 7, 2003), 642-643.

Jennifer Lansing, Distribution of Values of the Binomial Coefficients and the Stern Sequence, Journal of Integer Sequences,  16 (2013), #13.3.7.

Jennifer Lansing, Largest Values for the Stern Sequence, J. Integer Seqs., 17 (2014), #14.7.5.

D. H. Lehmer, On Stern's Diatomic Series, Amer. Math. Monthly 36(1) 1929, pp. 59-67. [Annotated and corrected scanned copy.]

Julien Leroy, Michel Rigo, Manon Stipulanti, Counting the number of non-zero coefficients in rows of generalized Pascal triangles, Discrete Mathematics 340 (2017), 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.

Mathematical Problems, Problem number 169 - Knut Angstrom (angstrom.knut(AT)telia.com), May 05 2009

S. Northshield, Stern's diatomic sequence 0, 1, 1, 2, 1, 3, 2, 3, 1, 4, ..., Amer. Math. Monthly, 117 (2010), 581-598.

S. Northshield, An Analogue of Stern's Sequence for Z[sqrt(2)], Journal of Integer Sequences, 18 (2015), #15.11.6.

Project Euler, Problem 169 - Exploring the number of different ways a number can be expressed as a sum of powers of 2.

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.

B. Reznick, Regularity properties of the Stern enumeration of the Rationals, JIS 11 (2008) 08.4.1

N. J. A. Sloane, Stern-Brocot or Farey Tree

R. P. Stanley and H. S. Wilf, Refining the Stern Diatomic Sequence, unpublished.

R. P. Stanley and H. S. Wilf, Refining the Stern Diatomic Sequence [Cached copy, with permission]

R. 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., 55 (1858), 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. 6, pp. 181-198, 2002.

Eric Weisstein's World of Mathematics, Calkin-Wilf Tree and Stern's Diatomic Series.

Index entries for "core" sequences

Index entries for fraction trees

Index entries for sequences related to Stern's sequences

Index entries for sequences related to trees

FORMULA

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

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)) 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->inf) 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 expression 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, else 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

a(n) = A287896(n-1) - 1*A288002(n-1) for n > 1;

a(n) = A007306(n-1) - 2*A288002(n-1) for n > 1. - I. V. Serov, Jun 14 2017

EXAMPLE

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)

MAPLE

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

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}] (* 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 *)

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

(PARI) A002487(n, a=1, b=0)=for(i=1, #n=binary(n), (n[i]&&b+=a)||a+=b); b \\ M. F. Hasler, Feb 12 2017

(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

(R)

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

(Scheme)

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

(R)

# Given n, compute directly 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])

}

# Example

n <- 91

a(n)     # 19

# Yosu Yurramendi, Dec 13 2016

(Python)

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

CROSSREFS

Cf. A000123, A000360, A001045, A002083, A011655, A020950, A026741, A037227, A046815, A049455, A070871, A070872, A071883, A073459, A084091, A101624, A126606, 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.

Sequence in context: A020651 A281392 A287051 * A263017 A245328 A060162

Adjacent sequences:  A002484 A002485 A002486 * A002488 A002489 A002490

KEYWORD

nonn,easy,nice,core,look,changed

AUTHOR

N. J. A. Sloane, Apr 30 1991

EXTENSIONS

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified October 22 09:59 EDT 2017. Contains 293761 sequences.