A348296 -id:A348296 - cp's OEIS frontend

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

David W. Wilson

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

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

Alois P. Heinz, Table of n, a(n) for n = 0..10000
Benoit Cloitre, Plot of a(n) for n=1 up to 100000

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

Cf. A048793, A133457; A348296; A000120.

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

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

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

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)

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

A355807 a(n) is the number at the apex of a triangle whose base contains the distinct powers of 2 summing to n (in ascending order), and each number in a higher row is the absolute difference of the two numbers directly below it; a(0) = 0.

Original entry on oeis.org

0, 1, 2, 1, 4, 3, 2, 1, 8, 7, 6, 5, 4, 1, 2, 1, 16, 15, 14, 13, 12, 9, 10, 9, 8, 1, 2, 3, 4, 3, 2, 1, 32, 31, 30, 29, 28, 25, 26, 25, 24, 17, 18, 13, 20, 19, 18, 17, 16, 1, 2, 11, 4, 5, 6, 3, 8, 7, 6, 3, 4, 1, 2, 1, 64, 63, 62, 61, 60, 57, 58, 57, 56, 49, 50

Offset: 0

Rémy Sigrist, Jul 18 2022

This sequence has similarities with A334387.

			For n = 27:
- we have the following triangle:
            3
          5   2
        1   6   8
      1   2   8  16
- so a(27) = 3.

Rémy Sigrist, Table of n, a(n) for n = 0..8191
Index entries for sequences related to binary expansion of n

See A355808, A355809, A355810 and A355811 for other variants.

Cf. A133457, A334387, A348296.

a(n) = { my (b=vector(hammingweight(n))); for (k=1, #b, n-=b[k]=2^valuation(n,2)); while (#b>1, b=vector(#b-1, k, abs(b[k+1]-b[k]))); if (#b, b[1], 0) }

a(n) <= n with equality iff n = 0 or n is a power of 2.

a(2*n) = 2*a(n).

A355808 a(n) is the number at the apex of a triangle whose base contains the distinct powers of 2 summing to n (in ascending order), and each number in a higher row is the difference of the two numbers directly below it; a(0) = 0.

Original entry on oeis.org

0, 1, 2, 1, 4, 3, 2, 1, 8, 7, 6, 5, 4, 1, 2, 1, 16, 15, 14, 13, 12, 9, 10, 9, 8, 1, 2, -3, 4, 3, 2, 1, 32, 31, 30, 29, 28, 25, 26, 25, 24, 17, 18, 13, 20, 19, 18, 17, 16, 1, 2, -11, 4, -5, -6, -15, 8, 7, 6, 9, 4, 1, 2, 1, 64, 63, 62, 61, 60, 57, 58, 57, 56, 49

Offset: 0

Rémy Sigrist, Jul 18 2022

			For n = 27:
- we have the following triangle:
           -3
          5   2
        1   6   8
      1   2   8  16
- so a(27) = -3.

Rémy Sigrist, Table of n, a(n) for n = 0..8192
Index entries for sequences related to binary expansion of n

See A355807 for similar sequences.

Cf. A348296.

a(n) = { my (b=vector(hammingweight(n))); for (k=1, #b, n-=b[k]=2^valuation(n,2)); while (#b>1, b=vector(#b-1, k, b[k+1]-b[k])); if (#b, b[1], 0) }

a(n) <= n with equality iff n = 0 or n is a power of 2.

a(2*n) = 2*a(n).

A355809 a(n) is the number at the apex of a triangle whose base contains the distinct powers of 2 summing to n (in ascending order), and each number in a higher row is the sum of the two numbers directly below it; a(0) = 0.

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 6, 9, 8, 9, 10, 13, 12, 17, 18, 27, 16, 17, 18, 21, 20, 25, 26, 35, 24, 33, 34, 47, 36, 53, 54, 81, 32, 33, 34, 37, 36, 41, 42, 51, 40, 49, 50, 63, 52, 69, 70, 97, 48, 65, 66, 87, 68, 93, 94, 129, 72, 105, 106, 153, 108, 161, 162, 243, 64, 65

Offset: 0

Rémy Sigrist, Jul 18 2022

			For n = 27:
- we have the following triangle:
          47
        13  34
       3  10  24
     1   2   8  16
- so a(27) = 47.

Rémy Sigrist, Table of n, a(n) for n = 0..8192
Index entries for sequences related to binary expansion of n

See A355807 for similar sequences.

Cf. A048645, A348296.

a(n) = { my (b=vector(hammingweight(n))); for (k=1, #b, n-=b[k]=2^valuation(n, 2)); while (#b>1, b=vector(#b-1, k, b[k+1]+b[k])); if (#b, b[1], 0) }

a(n) >= n with equality iff n = 0 or n belongs to A048645.

a(2*n) = 2*a(n).

A355810 a(n) is the number at the apex of a triangle whose base contains the distinct powers of 2 summing to n (in ascending order), and each number in a higher row is the bitwise XOR of the two numbers directly below it; a(0) = 0.

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 6, 5, 8, 9, 10, 9, 12, 9, 10, 15, 16, 17, 18, 17, 20, 17, 18, 23, 24, 17, 18, 27, 20, 29, 30, 17, 32, 33, 34, 33, 36, 33, 34, 39, 40, 33, 34, 43, 36, 45, 46, 33, 48, 33, 34, 51, 36, 53, 54, 33, 40, 57, 58, 33, 60, 33, 34, 51, 64, 65, 66, 65

Offset: 0

Rémy Sigrist, Jul 18 2022

			For n = 27:
- we have the following triangle:
          27
         9  18
       3  10  24
     1   2   8  16
- so a(27) = 27.

Rémy Sigrist, Table of n, a(n) for n = 0..8192
Index entries for sequences related to binary expansion of n

See A355807 for similar sequences.

Cf. A143071, A348296.

a(n) = { my (b=vector(hammingweight(n))); for (k=1, #b, n-=b[k]=2^valuation(n,2)); while (#b>1, b=vector(#b-1, k, bitxor(b[k+1], b[k]))); if (#b, b[1], 0) }

a(n) <= n with equality iff n = 0 or n belongs to A143071.

a(2*n) = 2*a(n).

A378212 a(n) is the greatest nonnegative integer k such that there exists a strictly increasing integer sequence k = b_1 < b_2 < ... < b_t = n with the property that b_1 XOR b_2 XOR ... XOR b_t = 0, or 0 if there are no such k (when n is a power of 2).

Original entry on oeis.org

0, 0, 0, 1, 0, 2, 3, 4, 0, 6, 5, 8, 7, 10, 9, 12, 0, 14, 13, 16, 11, 18, 17, 20, 15, 22, 21, 24, 19, 26, 25, 28, 0, 30, 29, 32, 27, 34, 33, 36, 23, 38, 37, 40, 35, 42, 41, 44, 31, 46, 45, 48, 43, 50, 49, 52, 39, 54, 53, 56, 51, 58, 57, 60, 0, 62, 61, 64, 59, 66, 65, 68, 55, 70, 69, 72, 67, 74, 73, 76, 47, 78, 77

Offset: 0

Peter Kagey and Antti Karttunen, Nov 25 2024

nonn

Let's call the sequences mentioned in the definition as "zero-XOR sequences", and their first terms as "starters". a(n) is then the greatest possible starter for any zero-XOR sequence ending with n. a(2^k)'s are set to 0's, because there are no zero-XOR sequences ending with any power of two. That such a sequence exists for any n that is not a power of 2 can be seen from the n-th row of A348296. [This from Peter's PDF-proof at A359506]

With 0's removed this is a permutation of natural numbers.

			A table illustrating the first fifteen terms:
   n |a(n)| sequence
  ---+----+-------------------------------------------------------------
   0 |  0 |  0
   1 |  0 |  As 1 = 2^0, there are no zero-XOR sequences ending with it
   2 |  0 |  (ditto, 2 = 2^1)
   3 |  1 |  1 XOR  2 XOR  3
   4 |  0 |  4 = 2^2
   5 |  2 |  2 XOR  3 XOR  4 XOR  5
   6 |  3 |  3 XOR  5 XOR  6
   7 |  4 |  4 XOR  5 XOR  6 XOR  7
   8 |  0 |  8 = 2^3
   9 |  6 |  6 XOR  7 XOR  8 XOR  9
  10 |  5 |  5 XOR  6 XOR  9 XOR 10
  11 |  8 |  8 XOR  9 XOR 10 XOR 11
  12 |  7 |  7 XOR 11 XOR 12
  13 | 10 | 10 XOR 11 XOR 12 XOR 13
  14 |  9 |  9 XOR 10 XOR 13 XOR 14
  ---+----+-------------------------------------------------------------
Note that there are often other solutions for a zero-XOR sequence ending with n, as for example the terms taken from the n-th row of A348296, followed by n, like for example [2, 8, 10] for 10, [1, 2, 8, 11] for 11, or [2, 4, 8, 14] for 14, but in those cases the starting term is not the greatest possible starter for a sequence ending with n that satisfies the condition.

Antti Karttunen, Table of n, a(n) for n = 0..65537

Left inverse of A359506.

Cf. A131577 (positions of 0's), A348296.

up_to = 65537;
A359506(n) = if(n==0, return (0), my (x=[n], y); for (m=n+1, oo, if (vecmin(y=[bitxor(v, m) | v<-x])==0, return (m), x=setunion(x, Set(y))))); \\ From A359506.
A378212list(up_to_n) = { my(v=vector(up_to_n), k); for(n=1, up_to_n, k=A359506(n); if(k <= up_to_n, if(0==v[k], v[k]=n, print("Not injective! A359506(",v[k],")=A359506("n")="k); return(1/0)))); (v); };
v378212 = A378212list(up_to);
A378212(n) = if(!n,n,v378212[n]);

For all n >= 0, a(A359506(n)) = n.

A355811 a(n) is the number at the apex of a triangle whose base contains the distinct powers of 2 summing to n (in ascending order), and each number in a higher row is the product of the two numbers directly below it; a(0) = 1.

Original entry on oeis.org

1, 1, 2, 2, 4, 4, 8, 16, 8, 8, 16, 32, 32, 128, 256, 4096, 16, 16, 32, 64, 64, 256, 512, 8192, 128, 1024, 2048, 65536, 4096, 524288, 1048576, 4294967296, 32, 32, 64, 128, 128, 512, 1024, 16384, 256, 2048, 4096, 131072, 8192, 1048576, 2097152, 8589934592, 512

Offset: 0

Rémy Sigrist, Jul 18 2022

			For n = 27:
- we have the following triangle:
           65536
         32  2048
       2    16   128
    1     2     8    16
- so a(27) = 65536.

Index entries for sequences related to binary expansion of n

See A355807 for similar sequences.

Cf. A048896, A348296.

a(n) = { my (b=vector(hammingweight(n))); for (k=1, #b, n-=b[k]=2^valuation(n, 2)); while (#b>1, b=vector(#b-1, k, b[k+1]*b[k])); if (#b, b[1], 1) }

a(n) = n iff n is a power of 2.

a(2*n) = a(n) * 2^A048896(n-1) for any n > 0.

cp's OEIS Frontend

A033922 Base-2 digital convolution sequence.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

PARI

PARI

Formula

Extensions

A355807 a(n) is the number at the apex of a triangle whose base contains the distinct powers of 2 summing to n (in ascending order), and each number in a higher row is the absolute difference of the two numbers directly below it; a(0) = 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A355808 a(n) is the number at the apex of a triangle whose base contains the distinct powers of 2 summing to n (in ascending order), and each number in a higher row is the difference of the two numbers directly below it; a(0) = 0.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

A355809 a(n) is the number at the apex of a triangle whose base contains the distinct powers of 2 summing to n (in ascending order), and each number in a higher row is the sum of the two numbers directly below it; a(0) = 0.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

A355810 a(n) is the number at the apex of a triangle whose base contains the distinct powers of 2 summing to n (in ascending order), and each number in a higher row is the bitwise XOR of the two numbers directly below it; a(0) = 0.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

A378212 a(n) is the greatest nonnegative integer k such that there exists a strictly increasing integer sequence k = b_1 < b_2 < ... < b_t = n with the property that b_1 XOR b_2 XOR ... XOR b_t = 0, or 0 if there are no such k (when n is a power of 2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A355811 a(n) is the number at the apex of a triangle whose base contains the distinct powers of 2 summing to n (in ascending order), and each number in a higher row is the product of the two numbers directly below it; a(0) = 1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula