login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 26
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 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,4
COMMENTS
Minima are at n=2^i-2, maxima at 2^i-1, zeros at A083866.
a(n) has parity of Thue-Morse sequence on {0,1} (A010060).
a(n) = A000120(n) for all n in A060142.
The composer Per Nørgård's name is also written in the OEIS as Per Noergaard.
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
From Antti Karttunen, Mar 09 2019: (Start)
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:
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
etc.
Sequences A323907, A323908 and A323909 are in bijective correspondence with this sequence and their terms are all nonnegative.
(End)
LINKS
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], Voyage into the golden screen, on YouTube.
Ralf Stephan, Divide-and-conquer generating functions. I. Elementary sequences, arXiv:math/0307027 [math.CO], 2003.
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.
a(n) = A343029(n) - A343030(n).
(End)
-(log_2(n+2)-1) <= a(n) <= log_2(n+1). - Charles R Greathouse IV, Nov 15 2022
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 *)
PROG
(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
(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
(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
CROSSREFS
Cf. A083866 (indices of 0's), A256187 (first differences), A010060 (mod 2), A343029, A343030.
Sequence in context: A346148 A262781 A157218 * A157225 A055347 A055288
KEYWORD
sign,nice,easy,hear
AUTHOR
Jorn B. Olsson (olsson(AT)math.ku.dk)
EXTENSIONS
Edited by Ralf Stephan, Mar 07 2003
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 25 17:15 EDT 2024. Contains 373706 sequences. (Running on oeis4.)