%I M0048 #92 Jan 15 2022 09:50:46
%S 0,1,1,0,1,-1,0,1,1,-2,-1,1,0,1,1,0,1,-3,-2,1,-1,2,1,-1,0,1,1,0,1,-1,
%T 0,1,1,-4,-3,1,-2,3,1,-2,-1,3,2,-1,1,-2,-1,1,0,1,1,0,1,-1,0,1,1,-2,-1,
%U 1,0,1,1,0,1,-5,-4,1,-3,4,1,-3,-2,5,3,-2,1,-3,-2,1,-1,4,3,-1,2,-3,-1,2,1,-3,-2,1,-1,2,1,-1,0,1,1,0,1,-1,0,1,1
%N a(0) = 0, a(1) = 1, a(2n) = a(n), a(2n+1) = a(n+1) - a(n).
%C If "-" in the definition is changed to "+", we get Stern's diatomic sequence A002487.
%C Sequence is 2-regular.
%C Let M = a triangular matrix with (1, 1, -1, 0, 0, 0, ...) in every column >k=1 shifted down twice from the previous column. Then A005590 starting with 1 = lim_{n->infinity} M^n, the left-shifted vector considered as a sequence. - _Gary W. Adamson_, Apr 13 2010
%C a(A001969(n)) <= 0; a(A000069(n)) > 0. - _Reinhard Zumkeller_, Apr 11 2012
%D B. Reznick, A new sequence with many properties, Abstract 809-10-185, Abstracts Amer. Math. Soc., 5 (1984), p. 16. [See link below]
%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="/A005590/b005590.txt">Table of n, a(n) for n = 0..10000</a>
%H J.-P. Allouche and M. Mendes France, <a href="http://arxiv.org/abs/1202.0211">Stern-Brocot polynomials and power series</a>, arXiv preprint arXiv:1202.0211 [math.NT], 2012.
%H 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 Michael Gilleland, <a href="/selfsimilar.html">Some Self-Similar Integer Sequences</a>
%H Bruce Reznick, <a href="http://projecteuclid.org/euclid.ijm/1256045729">Some extremal problems for continued fractions</a>, Ill. J. Math., 29 (1985), 261-279.
%H Bruce Reznick, <a href="/A005590/a005590.png">Letter to N. J. A. Sloane, Jun 03 1991</a>; also annotated scanned copy of B. Reznick, A new sequence with many properties, Abstract 809-10-185, Abstracts Amer. Math. Soc., 5 (1984), p. 16.
%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.
%F G.f.: x*Product_{k>=0} (1+x^(2^k) - x^2^(k+1)). - _Ralf Stephan_, Apr 26 2003
%F Conjecture: a(3n)=0 iff n in A003714. - _Ralf Stephan_, May 02 2003
%F a(n) = Sum_{k=0..n-1} (-1)^A010060(n-k-1)*(binomial(k, n-k-1) mod 2). - _Paul Barry_, Mar 26 2005
%F G.f. satisfies A(x) = (1 + 1/x - x) * A(x^2). - _Michael Somos_, Sep 17 2003
%F limsup log(|a(n)|)/(log n) = 0.4309... [Reznick] - _N. J. A. Sloane_, Jul 23 2016
%F From _Chai Wah Wu_, Dec 20 2016: (Start)
%F a(2^k*n+1) = a(n+1) - k*a(n);
%F a(2^k*n+3) = a(n) for k >= 2;
%F a(2^k*n+5) = -a(2^(k-1)*n+1) for k >= 3;
%F a(2^k*n+7) = a(2^(k-2)*n+1) for k >= 4;
%F a(2^k*n+2^k-1) = a(n) if k is even;
%F a(2^k*n+2^k-1) = a(n+1)-a(n)= a(2*n+1) if k is odd.
%F This implies that
%F a(2^k+1) = 1-k;
%F a(2^k+3) = 1 for k >= 2;
%F a(2^k+5) = k-2 for k >= 3;
%F a(2^k+7) = 3-k for k >= 4;
%F a(2^k-1) = 0 if k is even;
%F a(2^k-1) = 1 if k is odd.
%F (End)
%e G.f. = x + x^2 + x^4 - x^5 + x^7 + x^8 - 2*x^9 - x^10 + x^12 + x^13 + x^14 + ...
%p A005590 := proc(n) option remember; if n <= 1 then n; elif n mod 2 = 0 then A005590(n/2); else A005590((n+1)/2)-A005590((n-1)/2); fi; end;
%t a[0] = 0; a[1] = 1; a[n_] := a[n] = If[OddQ[n], a[(n-1)/2 + 1] - a[(n-1)/2], a[n/2]]; Table[a[n], {n, 0, 104}] (* _Jean-François Alcover_, Nov 27 2012 *)
%o (PARI) {a(n) = if( n<=1, n>0, if(n%2, a(n\2+1) - a(n\2), a(n/2)))}; /* _Michael Somos_, Sep 17 2003 */
%o (Haskell)
%o import Data.List (transpose)
%o a005590 n = a005590_list !! n
%o a005590_list = 0 : 1 : concat (tail $ transpose
%o [a005590_list, zipWith (-) (tail a005590_list) a005590_list])
%o -- _Reinhard Zumkeller_, Apr 11 2012
%o (Python)
%o l=[0, 1]
%o for n in range(2, 101):
%o l.append(l[n//2] if n%2==0 else l[(n + 1)//2] - l[(n - 1)//2])
%o print(l) # _Indranil Ghosh_, Jun 28 2017
%Y Cf. A002487, A182093 (partial sums).
%K sign,nice,easy,look
%O 0,10
%A _N. J. A. Sloane_
%E More terms from Antonio G. Astudillo (afg_astudillo(AT)lycos.com), Mar 28 2003
%E Signs corrected by _Ralf Stephan_, Apr 26 2003