

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^i2, maxima at 2^i1, zeros at A083866.
a(n) has parity of ThueMorse sequence on {0,1} (A010060).
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 12tone 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 (totone, 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
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



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)/[1x^(2*2^k)] * prod{l=0, k1, x^(2^l)1}}.
The g.f. satisfies F(x^2)*(1x) = F(x)x/(1x^2).
Zumkeller's formula implies that a(2n) = a(n), and so a(n) = a(4n) = a(16n) = ....  N. J. A. Sloane, Dec 31 2018
a(n) = (1)^t * (t+1  a(n1)) where t = A007814(n) is the 2adic valuation of n.
(End)


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((n1)/2)+1); fi; end;


MATHEMATICA

a[n_?EvenQ] := a[n]= a[n/2]; a[0]=0; a[n_] := a[n]= a[(n1)/2]+1; Table[a[n], {n, 0, 85}](* JeanFranç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])
(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:]))
(Python) # via recursion
from functools import lru_cache
@lru_cache(maxsize=None)
def a(n): return 0 if n == 0 else (a((n1)//2)+1 if n%2 else a(n//2))
(Python)
from itertools import groupby
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)


CROSSREFS



KEYWORD



AUTHOR

Jorn B. Olsson (olsson(AT)math.ku.dk)


EXTENSIONS



STATUS

approved



