A033922 Base-2 digital convolution sequence.

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, 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, 3, 4, 4, 5, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5

Offset

0,4

Comments

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

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

Links

Alois P. Heinz, Table of n, a(n) for n = 0..10000

Benoit Cloitre, Plot of a(n) for n=1 up to 100000

Example

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

Maple

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

Prog

(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 */
(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 */

Crossrefs

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

Sequence in context: A367758 A358370 A319688 * A008624 A059169 A026922

Adjacent sequences: A033919 A033920 A033921 * A033923 A033924 A033925

Keyword

nonn,base

Author

David W. Wilson

Extensions

Edited by Franklin T. Adams-Watters, Jul 13 2011

Status

approved