%I A002487 M0141 N0056
%S A002487 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,
%T A002487 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,
%U A002487 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 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).
%C A002487 Also called fusc(n).
%C A002487 a(n)/a(n+1) runs through all the reduced nonnegative rationals exactly
once [Stern; Calkin and Wilf]
%C A002487 If the terms are written as an array:
%C A002487 1
%C A002487 1,2
%C A002487 1,3,2,3
%C A002487 1,4,3,5,2,5,3,4
%C A002487 1,5,4,7,3,8,5,7,2,7,5,8,3,7,4,5
%C A002487 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
%C A002487 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
%C A002487 Number of odd Stirling numbers S_2(n+1,2r+1) [Carlitz]
%C A002487 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 A002487 a(n+1) = number of alternating bit sets in n (see Finch).
%C A002487 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
%C A002487 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]
%C A002487 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]
%C A002487 a(n+1) = number of odd binomial(n-k,k),0<=2k<n. [Carlitz].
%C A002487 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
%C A002487 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
%C A002487 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]
%D A002487 M. Aigner and G. M. Ziegler, Proofs from THE BOOK, 3rd ed., Berlin, Heidelberg,
New York: Springer-Verlag, 2004, p. 97.
%D A002487 J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoretical
Computer Sci., 98 (1992), 163-197.
%D A002487 J.-P. Allouche and J. Shallit, The ring of k-regular sequences, II, Theoret.
Computer Sci., 307 (2003), 3-29.
%D A002487 E. R. Berlekamp, J. H. Conway and R. K. Guy, Winning Ways, Academic Press,
NY, 2 vols., 1982, see p. 114.
%D A002487 M. Bicknell-Johnson, Stern's Diatomic Array Applied to Fibonacci Representations,
" Fibonacci Quarterly 41 (2003), pp. 169-180.
%D A002487 N. Calkin and H. S. Wilf, Recounting the rationals, Amer. Math. Monthly,
107 (No. 4, 2000), pp. 360-363.
%D A002487 L. Carlitz, A problem in partitions related to the Stirling numbers,
Bull. Amer. Math. Soc., 70(2) (1964), pp. 275-278.
%D A002487 L. Carlitz, A problem in partitions related to the Stirling numbers,
Riv. Mat. Univ. Parma, (2) 5 (1964), 61-75.
%D A002487 Courtright, K. M. and Sellers, J. A., Arithmetic Properties for Hyper
m-ary Partitions, INTEGERS 4 (2004), Article A6
%D A002487 G. De Rham, Un peu de mathematiques a propos d'une courbe plane, Elemente
der Math. 2 (1947), pp. 73-76 and 89-97.
%D A002487 E. Dijkstra, Selected Writings on Computing, Springer, 1982, p. 232 (sequence
is called fusc).
%D A002487 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.
%D A002487 S. R. Finch, Mathematical Constants, Cambridge, 2003, Section 2.16.3;
pp. 148-149.
%D A002487 G. Everest, A. van der Poorten, I. Shparlinski and T. Ward, Recurrence
Sequences, Amer. Math. Soc., 2003; see esp. p. 255.
%D A002487 R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley,
Reading, MA, 1990, p. 117.
%D A002487 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 A002487 D. E. Knuth, Problem 10906, American Mathematical Monthly; solution by
Moshe Newman, American Mathematical Monthly, 110 (No. 7, 2003), 642-643.
%D A002487 T. Koshy, Fibonacci and Lucas numbers with applications, Wiley, 2001,
p. 98.
%D A002487 D. H. Lehmer, On Stern's Diatomic Series, Amer. Math. Monthly 36(1) 1929,
pp. 59-67.
%D A002487 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.
%D A002487 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973
(includes this sequence).
%D A002487 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences,
Academic Press, 1995 (includes this sequence).
%D A002487 M. A. Stern, Ueber eine zahlentheoretische Funktion, J. Reine Angew.
Math., 55 (1858), 193-220.
%H A002487 T. D. Noe, <a href="b002487.txt">Table of n, a(n) for n = 0..10000</a>
%H A002487 J.-P. Allouche, M. Mendes France, A. Lubiw, A.J. van der Poorten and
J. Shallit, <a href="http://www.lri.fr/~allouche/bibliorecente.html">
Convergents of folded continued fractions</a>
%H A002487 J.-P. Allouche and J. Shallit, <a href="http://www.cs.uwaterloo.ca/~shallit/
Papers/as0.ps">The ring of k-regular sequences</a>, Theoretical Computer
Sci., 98 (1992), 163-197.
%H A002487 J.-P. Allouche and J. Shallit, <a href="http://www.lri.fr/~allouche/kreg2.ps">
The Ring of k-regular Sequences, II</a>
%H A002487 L. Carlitz, <a href="a002487abs1.html">A problem in partitions related
to the Stirling numbers (abstract)</a>
%H A002487 E. W. Dijkstra, <a href="http://www.cs.utexas.edu/users/EWD/ewd05xx/EWD570.PDF">
An exercise for Dr. R. M. Burstall</a>
%H A002487 E. W. Dijkstra, <a href="http://www.cs.utexas.edu/users/EWD/ewd05xx/EWD578.PDF">
More about the function ``fusc''</a>
%H A002487 S. 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)
%H A002487 Michael Gilleland, <a href="selfsimilar.html">Some Self-Similar Integer
Sequences</a>
%H A002487 B. Hayes, <a href="http://www.americanscientist.org/content/AMSCI/AMSCI/
ArticleAltFormat/200353145619_146.ps">On the Teeth of Wheels</a>
%H A002487 N. J. A. Sloane, <a href="stern_brocot.html">Stern-Brocot or Farey Tree</
a>
%H A002487 R. Stephan, <a href="http://arXiv.org/abs/math.CO/0307027">Divide-and-conquer
generating functions. I. Elementary sequences</a>
%H A002487 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/
SternsDiatomicSeries.html">Stern's Diatomic Series</a>
%H A002487 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/
Calkin-WilfTree.html">Calkin-Wilf Tree</a>
%H A002487 Thomas Wieder, <a href="http://www.thomas-wieder.privat.t-online.de/">
HomePage</a>.
%H A002487 H. S. Wilf, <a href="http://www.cis.upenn.edu/~wilf/reprints.html">Recounting
the Rationals</a> (with N. Calkin)
%H A002487 <a href="Sindx_St.html#Stern">Index entries for sequences related to
Stern's sequences</a>
%H A002487 <a href="Sindx_Cor.html#core">Index entries for "core" sequences</a>
%H A002487 <a href="Sindx_Tra.html#trees">Index entries for sequences related to
trees</a>
%F A002487 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
%F A002487 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
%F A002487 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 A002487 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
%F A002487 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
%F A002487 a(n)=sum{k=0..n-1, binomial(k, n-k-1) mod 2}; - Paul Barry (pbarry(AT)wit.ie),
Mar 26 2005
%F A002487 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
%F A002487 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 A002487 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
%F A002487 G.f.: x Product_{k>=0} (1+x^2^k+x^2^{k+1}). [Carlitz]
%F A002487 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
%F A002487 A079978(n)=(1+e^(i*pi*A002487(n)))/2, i=sqrt(-1); - Paul Barry (pbarry(AT)wit.ie),
Jan 14 2005
%F A002487 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
%F A002487 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 A002487 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 A002487 a(2^n + k) = a(2^n - k) + a(k) (0 <= k <= 2^n). - Arie Werksma (werksma(AT)tiscali.nl),
Apr 18 2008
%F A002487 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
%F A002487 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
%F A002487 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 A002487 a(n) = A126606(n + 1) / 2. [From Reikku Kulon (reikku(AT)gmail.com),
Oct 05 2008]
%F A002487 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]
%p A002487 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;
%p A002487 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.
%p A002487 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
%t A002487 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}]
%t A002487 Onemore[l_] := Transpose[{l, l+RotateLeft[l]}]//Flatten NestList[Onemore,
{1}, 5]//Flatten gives [a(1), ...] - Takashi Tokita Mar 09 2003
%t A002487 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
%o A002487 (PARI) a(n)=if(n<2,n>0,a(n\2)+if(n%2,a(n\2+1)))
%o A002487 (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 */
%o A002487 (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]
%Y A002487 Cf. A084091.
%Y A002487 If the 1's are replaced by pairs of 1's we obtain A049456.
%Y A002487 Inverse: A020946. Cf. A020950, A046815, A070871, A070872, A071883.
%Y A002487 A002487(A001045(n))=A000045(n). A002487(A062092(n))=A000032(n+1).
%Y A002487 See also A064881-A064886 (Stern-Brocot subtrees). A column of A072170.
%Y A002487 Cf. A001045, A002083.
%Y A002487 Cf. A073459, A000123.
%Y A002487 Cf. A126606, A049455 [From Reikku Kulon (reikku(AT)gmail.com), Oct 05
2008]
%Y A002487 A011655. [From Reinhard Zumkeller (reinhard.zumkeller(AT)gmail.com),
Dec 27 2008]
%Y A002487 Sequence in context: A070940 A020651 A160232 this_sequence A060162 A026730
A075256
%Y A002487 Adjacent sequences: A002484 A002485 A002486 this_sequence A002488 A002489
A002490
%K A002487 nonn,easy,nice,core
%O A002487 0,4
%A A002487 N. J. A. Sloane (njas(AT)research.att.com).
%E A002487 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).
%E A002487 More terms from Arie Werksma (Werksma(AT)Tiscali.nl), Jul 11 2008
%E A002487 Formula corrected by Mats Granvik (mats.granvik(AT)abo.fi), Oct 10 2009
|
