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

Author

David W. Wilson

Keywords

• nonn
• base

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

Number of 0's in Goodstein base-2 hereditary representation of n. For example, a(266)=5 once that 266 = 2^(2^(2^(2^0)+2^0)) + 2^(2^(2^0)+2^0) + 2^(2^0). - Flávio V. Fernandes, Jul 22 2025

Examples

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

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

Crossrefs

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

Cf. A048793, A133457; A348296; A000120.

Programs

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

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

Formula

From Flávio V. Fernandes, Jul 31 2025: (Start)

a(n) = a(2^n).

a(n) = Sum_{k=1..A000120(n)} a(A048793(n,k)-1) for n >= 1. (End)

Extensions

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