A033922 - OEIS

%I #38 Apr 13 2021 23:32:00

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

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

%U 3,4,4,5,4,5,5,6,5,6,6,7,3,4,4,5,4,5

%N Base-2 digital convolution sequence.

%C Definition: a(0) = 1; for n > 0, let the base-2 representation of n be 2^k_1 + ... + 2^k_i, then a(n) = a(k_1) + ... + a(k_i).

%C The sequence can be constructed as follows. Let r(n)=[x(1),x(2),...,x(2^n)] denote a run of 2^n elements. Then r(n+1) is a run of length 2^(n+1) defined as the concatenation of r(n) and [x(1)+x(n), x(2)+x(n), ..., x(2^n)+x(n)]. Letting x(1)=0 and x(2)=1 we get r(1)=[0,1], r(2)=[0, 1, 1, 2], r(3)=[0, 1, 1, 2, 1, 2, 2, 3], r(4)=[0, 1, 1, 2, 1, 2, 2, 3, 2, 3, 3, 4, 3, 4, 4, 5], etc. Replacing the leading zero by 1 in r(infinity) we get A033922. - _Benoit Cloitre_, Jan 10 2013

%H Alois P. Heinz, <a href="/A033922/b033922.txt">Table of n, a(n) for n = 0..10000</a>

%H Benoit Cloitre, <a href="/A033922/a033922.png">Plot of a(n) for n=1 up to 100000</a>

%e For example, 6 = 2^2 + 2^1, so a(6) = a(2) + a(1) = 2.

%p a:= proc(n) option remember; local c, m, t; if n=0 then 1 else m:= n; c:=0; for t from 0 while m<>0 do c:= c+ `if`(irem(m, 2, 'm')=1, a(t), 0) od; c fi end: seq(a(n), n=0..120);  # _Alois P. Heinz_, Jul 13 2011

%o (PARI) al(n)=local(v,k,e);v=vector(n+1);v[1]=1;for(m=1,n,k=m;e=0;while(k>0,if(k%2,v[m+1]+=v[e+1]);e++;k\=2));v /* _Benoit Cloitre_, Jan 10 2013 */

%o (PARI) /* to compute quickly 2^m terms of the sequence */ m=10;v=[0,1];for(n=2,m,v=concat(v,vector(2^n/2,i,v[i]+v[n])));a(n)=if(n<2,1,v[n]) /* _Benoit Cloitre_, Jan 16 2013 */

%Y Cf. A033639, A014221 (n such that a(n)=1), A206774 (first differences).

%K nonn,base

%O 0,4

%A _David W. Wilson_

%E Edited by _Franklin T. Adams-Watters_, Jul 13 2011