%I #114 Mar 02 2023 17:48:01
%S 0,1,-1,2,1,0,-2,3,-1,2,0,1,2,-1,-3,4,1,0,-2,3,0,1,-1,2,-2,3,1,0,3,-2,
%T -4,5,-1,2,0,1,2,-1,-3,4,0,1,-1,2,1,0,-2,3,2,-1,-3,4,-1,2,0,1,-3,4,2,
%U -1,4,-3,-5,6,1,0,-2,3,0,1,-1,2,-2,3,1,0,3,-2,-4,5,0,1,-1,2,1,0
%N The Danish composer Per Nørgård's "infinity sequence", invented in an attempt to unify in a perfect way repetition and variation: a(2n) = -a(n), a(2n+1) = a(n) + 1, a(0) = 0.
%C Minima are at n=2^i-2, maxima at 2^i-1, zeros at A083866.
%C a(n) has parity of Thue-Morse sequence on {0,1} (A010060).
%C a(n) = A000120(n) for all n in A060142.
%C The composer Per Nørgård's name is also written in the OEIS as Per Noergaard.
%C Comment from Michael Nyvang on the "iris" score on the "Voyage into the golden screen" video, Dec 31 2018: That is A004718 on the cover in the 12-tone tempered chromatic scale. The music - as far as I recall - is constructed from this base by choosing subsequences out of this sequence in what Per calls 'wave lengths', and choosing different scales modulo (to-tone, overtones on one fundamental, etc). There quite a lot more to say about this, but I believe this is the foundation. - _N. J. A. Sloane_, Jan 05 2019
%C From _Antti Karttunen_, Mar 09 2019: (Start)
%C This sequence can be represented as a binary tree. After a(0) = 0 and a(1) = 1, each child to the left is obtained by negating the parent node's contents, and each child to the right is obtained by adding one to the parent's contents:
%C 0
%C |
%C ...................1...................
%C -1 2
%C 1......../ \........0 -2......../ \........3
%C / \ / \ / \ / \
%C / \ / \ / \ / \
%C / \ / \ / \ / \
%C -1 2 0 1 2 -1 -3 4
%C 1 0 -2 3 0 1 -1 2 -2 3 1 0 3 -2 -4 5
%C etc.
%C Sequences A323907, A323908 and A323909 are in bijective correspondence with this sequence and their terms are all nonnegative.
%C (End)
%H N. J. A. Sloane, <a href="/A004718/b004718.txt">Table of n, a(n) for n = 0..10000</a>
%H J.-P. Allouche and J. Shallit, <a href="http://www.math.jussieu.fr/~allouche/kreg2.ps">The Ring of k-regular Sequences, II</a>
%H J.-P. Allouche and J. 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.
%H Yu Hin Au, Christopher Drexler-Lemire and Jeffrey Shallit, <a href="https://doi.org/10.1080/17459737.2017.1299807">Notes and note pairs in Nørgård's infinity series</a>, Journal of Mathematics and Music, Volume 11, 2017, Issue 1, pages 1-19. - _N. J. A. Sloane_, Dec 31 2018
%H Christopher Drexler-Lemire and Jeffrey Shallit, <a href="http://arxiv.org/abs/1402.3091">Notes and Note-Pairs in Noergaard's Infinity Series</a>, arXiv:1402.3091 [math.CO], 2014.
%H Per Nørgård [Noergaard], <a href="https://www.youtube.com/watch?v=Q_FGImH1RWE">The infinity series</a>, on YouTube.
%H Per Nørgård [Noergaard], <a href="http://web.archive.org/web/20060224072530id_/http://www.pernoergaard.dk/ress/musexx/mu01.mp3">First 128 notes of the infinity series (MP3 Recording)</a>
%H Per Nørgård [Noergaard], <a href="https://www.youtube.com/watch?v=wc8GvMkjGBc">Voyage into the golden screen</a>, on YouTube.
%H Per Nørgård [Noergaard], <a href="http://web.archive.org/web/20060224072542id_/http://www.pernoergaard.dk/ress/musexx/m1110356.mp3">Voyage into the golden screen (MP3 Recording)</a>
%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 Robert Walker, <a href="http://robertinventor.com/ftswiki/Self_Similar_Sloth_Canon_Number_Sequences">Self Similar Sloth Canon Number Sequences</a>
%H Wikipedia, <a href="http://de.wikipedia.org/wiki/Unendlichkeitsreihe">Unendlichkeitsreihe</a>
%H Jon Wild, <a href="/A004718/a004718_1.txt">Comments on the musical score in the YouTube illustrations for the "Iris" and "Voyage into the golden screen" videos</a>
%H <a href="/index/Mu#music">Index entries for sequences related to music</a>
%F Write n in binary and read from left to right, starting with 0 and interpreting 1 as "add 1" and 0 as "change sign". For example 19 = binary 10011, giving 0 -> 1 -> -1 -> 1 -> 2 -> 3, so a(19) = 3.
%F G.f.: sum{k>=0, x^(2^k)/[1-x^(2*2^k)] * prod{l=0, k-1, x^(2^l)-1}}.
%F The g.f. satisfies F(x^2)*(1-x) = F(x)-x/(1-x^2).
%F a(n) = (2 * (n mod 2) - 1) * a(floor(n/2)) + n mod 2. - _Reinhard Zumkeller_, Mar 20 2015
%F Zumkeller's formula implies that a(2n) = -a(n), and so a(n) = a(4n) = a(16n) = .... - _N. J. A. Sloane_, Dec 31 2018
%F From _Kevin Ryde_, Apr 17 2021: (Start)
%F a(n) = (-1)^t * (t+1 - a(n-1)) where t = A007814(n) is the 2-adic valuation of n.
%F a(n) = A343029(n) - A343030(n).
%F (End)
%F -(log_2(n+2)-1) <= a(n) <= log_2(n+1). - _Charles R Greathouse IV_, Nov 15 2022
%p f:=proc(n) option remember; if n=0 then RETURN(0); fi; if n mod 2 = 0 then RETURN(-f(n/2)); else RETURN(f((n-1)/2)+1); fi; end;
%t a[n_?EvenQ] := a[n]= -a[n/2]; a[0]=0; a[n_] := a[n]= a[(n-1)/2]+1; Table[a[n], {n, 0, 85}](* _Jean-François Alcover_, Nov 18 2011 *)
%t Table[Fold[If[#2 == 0, -#1, #1 + 1] &, IntegerDigits[n, 2]], {n, 0, 85}] (* _Michael De Vlieger_, Jun 30 2016 *)
%o (PARI) a=vector(100); a[1]=1; a[2]=-1; for(n=3,#a,a[n]=if(n%2,a[n\2]+1,-a[n\2])); a \\ _Charles R Greathouse IV_, Nov 18 2011
%o (Haskell)
%o import Data.List (transpose)
%o a004718 n = a004718_list !! n
%o a004718_list = 0 : concat
%o (transpose [map (+ 1) a004718_list, map negate $ tail a004718_list])
%o -- _Reinhard Zumkeller_, Mar 19 2015, Nov 10 2012
%o (Python) # from first formula
%o from functools import reduce
%o def f(s, b): return s + 1 if b == '1' else -s
%o def a(n): return reduce(f, [0] + list(bin(n)[2:]))
%o print([a(n) for n in range(86)]) # _Michael S. Branicky_, Apr 03 2021
%o (Python) # via recursion
%o from functools import lru_cache
%o @lru_cache(maxsize=None)
%o def a(n): return 0 if n == 0 else (a((n-1)//2)+1 if n%2 else -a(n//2))
%o print([a(n) for n in range(86)]) # _Michael S. Branicky_, Apr 03 2021
%o (Python)
%o from itertools import groupby
%o def A004718(n):
%o c = 0
%o for k, g in groupby(bin(n)[2:]):
%o c = c+len(list(g)) if k == '1' else (-c if len(list(g))&1 else c)
%o return c # _Chai Wah Wu_, Mar 02 2023
%Y Cf. A083866 (indices of 0's), A256187 (first differences), A010060 (mod 2), A343029, A343030.
%Y Variants: A256184, A256185, A255723, A323886, A323887, A323907, A323908, A323909.
%K sign,nice,easy,hear
%O 0,4
%A Jorn B. Olsson (olsson(AT)math.ku.dk)
%E Edited by _Ralf Stephan_, Mar 07 2003