

A004718


The Danish composer Per Norgard [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.


4



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).
a(n) = A000120(n) for all n in A060142.
The composer Per Norgard's name is also written in the OEIS as Per Noergaard.


REFERENCES

J.P. Allouche and J. Shallit, The ring of kregular sequences, II, Theoret. Computer Sci., 307 (2003), 329.


LINKS

N. J. A. Sloane, First 10000 terms
J.P. Allouche, J. Shallit, The Ring of kregular Sequences, II
Christopher DrexlerLemire, Jeffrey Shallit, Notes and NotePairs in Noergaard's Infinity Series, arXiv:1402.3091 [math.CO]
Per Noergaard [Norgard], Home Page
Per Noergaard [Norgard], "Voyage into the golden screen", 2nd movement
Per Noergaard [Norgard], "Voyage into the golden screen" (MP3 Recording)
Per Noergaard [Norgard], First 128 notes of the infinity series (MP3 Recording)
R. Stephan, Divideandconquer generating functions. I. Elementary sequences
Robert Walker, Self Similar Sloth Canon Number Sequences


FORMULA

Write n in binary and read from left to write, 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).


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 *)


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)
a004718 n = foldr ($) 0 $ noergaard n where
noergaard x  x == 0 = []
 d == 0 = negate : noergaard x'
 d == 1 = (+ 1) : noergaard x' where (x', d) = divMod x 2
 Reinhard Zumkeller, Nov 10 2012


CROSSREFS

Sequence in context: A145579 A167655 A157218 * A157225 A055347 A055288
Adjacent sequences: A004715 A004716 A004717 * A004719 A004720 A004721


KEYWORD

sign,nice,easy,hear


AUTHOR

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


EXTENSIONS

Edited by Ralf Stephan, Mar 07 2003


STATUS

approved



