0,4

Also called fusc(n).

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) except for n=0 or n=-1. If T(x):=-1/x and f(x)=y, then f(T(y))=T(x) except 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<=2k<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 (alex(AT)kolmogorov.com), 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 (Philippe.Flajolet(AT)inria.fr), Sep 06 2008

It appears that are also the odd entries in diagonals in Pascal's triangle at 45 degrees slope [From Javier Torres (adaycalledzero(AT)hotmail.com), Aug 06 2009]

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

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.

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.

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.

S. R. Finch, Mathematical Constants, Cambridge, 2003, Section 2.16.3; pp. 148-149.

G. Everest, A. van der Poorten, I. Shparlinski and T. Ward, Recurrence Sequences, Amer. Math. Soc., 2003; see esp. p. 255.

R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 117.

Hinz, A. M.; Klavzar, S; Milutinovic, U.; Parisse, D.; and Petr, C., Metric properties of the Tower of Hanoi graphs and Stern's diatomic sequence. European J. Combin. 26 (2005), no. 5, 693-708.

D. E. Knuth, Problem 10906, American Mathematical Monthly; solution by Moshe Newman, American Mathematical Monthly, 110 (No. 7, 2003), 642-643.

T. Koshy, Fibonacci and Lucas numbers with applications, Wiley, 2001, p. 98.

D. H. Lehmer, On Stern's Diatomic Series, Amer. Math. Monthly 36(1) 1929, pp. 59-67.

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

M. A. Stern, Ueber eine zahlentheoretische Funktion, J. Reine Angew. Math., 55 (1858), 193-220.

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

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)

Michael Gilleland, Some Self-Similar Integer Sequences

B. Hayes, On the Teeth of Wheels

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

R. Stephan, Divide-and-conquer generating functions. I. Elementary sequences

Eric Weisstein's World of Mathematics, Stern's Diatomic Series

Eric Weisstein's World of Mathematics, Calkin-Wilf Tree

Thomas Wieder, HomePage.

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

a(0) = 0; a(1) = 1; a(2k) = a(k); a(2k+1) = a(k) + a(k+1) generates the same sequence with an initial 0 - David W. Wilson

a(n+1) = (2k+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 Newman (dznewman(AT)netvision.net.il), 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 (benoit7848c(AT)orange.fr), Jan 18 2004

a(n)=sum{k=0..floor((n-1)/2), mod(binomial(n-k-1, k), 2)} - Paul Barry (pbarry(AT)wit.ie), Sep 13 2004

a(n)=sum{k=0..n-1, binomial(k, n-k-1) mod 2}; - Paul Barry (pbarry(AT)wit.ie), 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+2uvw-u^2w. - 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

For all integer n, a(-n)=-(-1)^n*a(n), a(n)=a(2n)sign(n)^n, a(n-1)+a(n)sign(n)=a(2n-1)sign(n)^n. - Michael Somos Sep 03 2006

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 (mike(AT)math.ucr.edu), Nov 06 2006

A079978(n)=(1+e^(i*pi*A002487(n)))/2, i=sqrt(-1); - Paul Barry (pbarry(AT)wit.ie), Jan 14 2005

a(n)=sum(K(k, n-k)*a(n - k),k=1..n), 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 (thomas.wieder(AT)t-online.de), 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. [From Reikku Kulon (reikku(AT)gmail.com), 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]. [From Mats Granvik, Gary W. Adamson (mats.granvik(AT)abo.fi), Oct 02 2009]

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;

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: # 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(2n+1), this program can be adapted for A007306 by replacing b := 0 by b := 1.

a := proc(n::integer) # A002487 Stern's diatomic series: a(0) = 0, a(1) = 1; for n >= 0, a(2n) = a(n), a(2n+1) = a(n) + a(n+1). local k; option remember; if n = 0 then 1 else add(K(k, n-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; - Thomas Wieder (thomas.wieder(AT)t-online.de), Jan 13 2008

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

(PARI) a(n)=if(n<2, n>0, a(n\2)+if(n%2, a(n\2+1)))

(PARI) {a(n)=if(n<0, -(-1)^n*a(-n), if(n<2, n>0, a(n\2)+if(n%2, a(n\2+1))))} /* Michael Somos Sep 03 2006 */

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

Cf. A084091.

If the 1's are replaced by pairs of 1's we obtain A049456.

Inverse: A020946. Cf. A020950, A046815, A070871, A070872, A071883.

A002487(A001045(n))=A000045(n). A002487(A062092(n))=A000032(n+1).

See also A064881-A064886 (Stern-Brocot subtrees). A column of A072170.

Cf. A001045, A002083.

Cf. A073459, A000123.

Cf. A126606, A049455 [From Reikku Kulon (reikku(AT)gmail.com), Oct 05 2008]

A011655. [From Reinhard Zumkeller (reinhard.zumkeller(AT)gmail.com), Dec 27 2008]

Adjacent sequences: A002484 A002485 A002486 this_sequence A002488 A002489 A002490

Sequence in context: A070940 A020651 A160232 this_sequence A060162 A026730 A075256

nonn,easy,nice,core,new

N. J. A. Sloane (njas(AT)research.att.com).

Additional references and comments from Leonard Smiley (smiley(AT)math.uaa.alaska.edu), Joshua Zucker (joshua.zucker(AT)stanfordalumni.org), Rick L. Shepherd (rshepherd2(AT)hotmail.com) 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 (mats.granvik(AT)abo.fi), Oct 10 2009