A004718 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.
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, -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, -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
Offset: 0
Links
- N. J. A. Sloane, Table of n, a(n) for n = 0..10000
- J.-P. Allouche and J. Shallit, The Ring of k-regular Sequences, II
- J.-P. Allouche and J. Shallit, The ring of k-regular sequences, II, Theoret. Computer Sci., 307 (2003), 3-29.
- Yu Hin Au, Christopher Drexler-Lemire and Jeffrey Shallit, Notes and note pairs in Nørgård's infinity series, Journal of Mathematics and Music, Volume 11, 2017, Issue 1, pages 1-19. - _N. J. A. Sloane_, Dec 31 2018
- Christopher Drexler-Lemire and Jeffrey Shallit, Notes and Note-Pairs in Noergaard's Infinity Series, arXiv:1402.3091 [math.CO], 2014.
- Per Nørgård [Noergaard], The infinity series, on YouTube.
- Per Nørgård [Noergaard], First 128 notes of the infinity series (MP3 Recording)
- Per Nørgård [Noergaard], Voyage into the golden screen, on YouTube.
- Per Nørgård [Noergaard], Voyage into the golden screen (MP3 Recording)
- Ralf Stephan, Divide-and-conquer generating functions. I. Elementary sequences, arXiv:math/0307027 [math.CO], 2003.
- Robert Walker, Self Similar Sloth Canon Number Sequences
- Wikipedia, Unendlichkeitsreihe
- Jon Wild, Comments on the musical score in the YouTube illustrations for the "Iris" and "Voyage into the golden screen" videos
- Index entries for sequences related to music
Crossrefs
Programs
-
Haskell
import Data.List (transpose) a004718 n = a004718_list !! n a004718_list = 0 : concat (transpose [map (+ 1) a004718_list, map negate $ tail a004718_list]) -- Reinhard Zumkeller, Mar 19 2015, Nov 10 2012
-
Maple
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;
-
Mathematica
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 *) Table[Fold[If[#2 == 0, -#1, #1 + 1] &, IntegerDigits[n, 2]], {n, 0, 85}] (* Michael De Vlieger, Jun 30 2016 *) -
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
-
PARI
apply( {A004718(n)=[n=if(b,n+1,-n)|b<-binary(n+n=0)];n}, [0..77]) \\ M. F. Hasler, Jun 13 2025 -
Python
# from first formula from functools import reduce def f(s, b): return s + 1 if b == '1' else -s def a(n): return reduce(f, [0] + list(bin(n)[2:])) print([a(n) for n in range(86)]) # Michael S. Branicky, Apr 03 2021
-
Python
# via recursion from functools import lru_cache @lru_cache(maxsize=None) def a(n): return 0 if n == 0 else (a((n-1)//2)+1 if n%2 else -a(n//2)) print([a(n) for n in range(86)]) # Michael S. Branicky, Apr 03 2021
-
Python
from itertools import groupby def A004718(n): c = 0 for k, g in groupby(bin(n)[2:]): c = c+len(list(g)) if k == '1' else (-c if len(list(g))&1 else c) return c # Chai Wah Wu, Mar 02 2023
Formula
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.
G.f.: sum{k>=0, x^(2^k)/[1-x^(2*2^k)] * prod{l=0, k-1, x^(2^l)-1}}.
The g.f. satisfies F(x^2)*(1-x) = F(x)-x/(1-x^2).
a(n) = (2 * (n mod 2) - 1) * a(floor(n/2)) + n mod 2. - Reinhard Zumkeller, Mar 20 2015
Zumkeller's formula implies that a(2n) = -a(n), and so a(n) = a(4n) = a(16n) = .... - N. J. A. Sloane, Dec 31 2018
From Kevin Ryde, Apr 17 2021: (Start)
a(n) = (-1)^t * (t+1 - a(n-1)) where t = A007814(n) is the 2-adic valuation of n.
-(log_2(n+2)-1) <= a(n) <= log_2(n+1). - Charles R Greathouse IV, Nov 15 2022
Extensions
Edited by Ralf Stephan, Mar 07 2003
Comments