login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A033922 Base-2 digital convolution sequence. 3
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 (list; graph; refs; listen; history; text; internal format)
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: A029363 A304708 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 23 05:01 EDT 2021. Contains 345395 sequences. (Running on oeis4.)