login
Start with first run [0,1] then, for n >= 2, the n-th run has length 2^n and is the concatenation of [a(1),a(2),...,a(2^n/2)] and [n-a(1),n-a(2),...,n-a(2^n/2)].
18

%I #39 May 14 2022 11:28:36

%S 0,1,2,1,3,2,1,2,4,3,2,3,1,2,3,2,5,4,3,4,2,3,4,3,1,2,3,2,4,3,2,3,6,5,

%T 4,5,3,4,5,4,2,3,4,3,5,4,3,4,1,2,3,2,4,3,2,3,5,4,3,4,2,3,4,3,7,6,5,6,

%U 4,5,6,5,3,4,5,4,6,5,4,5,2,3,4,3,5,4,3

%N Start with first run [0,1] then, for n >= 2, the n-th run has length 2^n and is the concatenation of [a(1),a(2),...,a(2^n/2)] and [n-a(1),n-a(2),...,n-a(2^n/2)].

%C Also the sum of the odd bisection (odd-indexed parts) of the (n-1)-th composition in standard order, where the k-th composition in standard order (graded reverse-lexicographic, A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. Note that this sequence counts {} as composition number 1 (instead of the usual 0). For example, composition number 741 in standard order is (2,1,1,3,2,1), with odd bisection (2,1,2), so a(742) = 2 + 1 + 2 = 5. - _Gus Wiseman_, Aug 24 2021

%F Let T(n)=A010060(n) then for n>=1 a(2n)=a(n)+1-T(n-1) and a(2n+1)=a(n+1)+T(n).

%F For n>=2 a(n) = a(ceiling(n/2))+T(n-1) hence:

%F a(n) = Sum_{k=0..ceiling(log(n-1)/log(2))} T(floor((n-1)/2^k)).

%F For k>=0 a(3*2^k+1)=1 (more precisely a(n)=1 iff n is in A103204), a(2^k+1)=k+1, a(5*2^k+1)=2, a(7*2^k+1)=k+2 etc.

%F From _Gus Wiseman_, Aug 18 2021: (Start)

%F a(n + 1) = (A029837(n) + A124754(n))/2.

%F a(n + 1) = A029837(n) - A346633(n).

%F a(n + 1) = A346633(n) - A124754(n).

%F a(n + 1) = A029837(A346702(n)).

%F (End)

%F From _Kevin Ryde_, May 14 2022: (Start)

%F a(n) = A000120(A006068(n-1)), binary weight of inverse binary Gray code.

%F a(n) = Sum_{k=1..A000120(n-1)} (-1)^(k-1) * A272020(n-1,k), alternating sum of 1-bit positions.

%F a(n) = A089215(n) - 1.

%F (End)

%e [0,1] -> [0,1] U [2-0,2-1] =

%e [0,1,2,1] -> [0,1,2,1] U [3-0,3-1,3-2,3-1] =

%e [0,1,2,1,3,2,1,2] etc.

%e From _Gus Wiseman_, Aug 08 2021: (Start)

%e As a triangle without the initial 0, row-lengths A000079:

%e 1

%e 2 1

%e 3 2 1 2

%e 4 3 2 3 1 2 3 2

%e 5 4 3 4 2 3 4 3 1 2 3 2 4 3 2 3

%e 6 5 4 5 3 4 5 4 2 3 4 3 5 4 3 4 1 2 3 2 4 3 2 3 5 4 3 4 2 3 4 3

%e (End)

%t Table[Total[First/@Partition[Append[Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse,0],2]],{n,0,100}] (* _Gus Wiseman_, Aug 08 2021 *)

%o (PARI)/* compute 2^15 terms */ v=[0,1];for(n=2,15,v=concat(v,vector(2^n/2,i,n-v[i]));a(n)=v[n];)

%o (PARI) a(n) = n--; my(s=1,ns); while((ns=n>>s), n=bitxor(n,ns); s<<=1); hammingweight(n); \\ _Kevin Ryde_, May 14 2022

%Y Cf. A010060 (Thue-Morse), A103204 (indices of 1's).

%Y Cf. A029837 (binary order), A000120 (binary weight), A006068 (inverse Gray), A272020 (bit positions).

%Y Cf. A089215.

%Y As a triangle: A000079 (row lengths), A001792 (row sums).

%Y Other composition part sums: A124754. A346633.

%Y Also the sum of row A346702(n-1) of A066099.

%Y Cf. A346697 (on prime indices).

%K nonn,tabf

%O 1,3

%A _Benoit Cloitre_, Jan 16 2013