cp's OEIS Frontend

This is the quite common, so-called "bittest" function, see PARI code. - M. F. Hasler, Jul 21 2013

For a given number m and a digit position k the corresponding sequence index n can be calculated by n(m, k) = m*(1 + floor(log_2(m))) - 2^(1 + floor(log_2(m))) + k + 1. For example: counted from right to left, the second digit of m = 13 (binary 1101) is '0'. Hence the sequence index is n = n(13, 2) = 39. - Hieronymus Fischer, May 05 2007

A070939(n) is the length of n-th row; A000120(n) is the sum of n-th row; A030101(n) is the n-th row seen as binary number; A000035(n) = T(n, 0). - Reinhard Zumkeller, Jun 17 2012

In other words, numbers whose binary representation consists of one or more repeating blocks with only one 1 in each block.

Also, fixed points of the permutations A139706 and A139708.

Each a(n) is a term of A064896 multiplied by some power of 2. As such, this sequence must also be a subsequence of A125121.

Also the numbers that uniquely index a Haar graph (i.e., 5 and 6 are not in the sequence since H(5) is isomorphic to H(6)). - Eric W. Weisstein, Aug 19 2017

From Gus Wiseman, Apr 04 2020: (Start)

The k-th composition in standard order (row k of A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions. This sequence lists all positive integers k such that the k-th composition in standard order is constant. For example, the sequence together with the corresponding constant compositions begins:

0: () 136: (4,4)

1: (1) 170: (2,2,2,2)

2: (2) 255: (1,1,1,1,1,1,1,1)

3: (1,1) 256: (9)

4: (3) 292: (3,3,3)

7: (1,1,1) 511: (1,1,1,1,1,1,1,1,1)

8: (4) 512: (10)

10: (2,2) 528: (5,5)

15: (1,1,1,1) 682: (2,2,2,2,2)

16: (5) 1023: (1,1,1,1,1,1,1,1,1,1)

31: (1,1,1,1,1) 1024: (11)

32: (6) 2047: (1,1,1,1,1,1,1,1,1,1,1)

36: (3,3) 2048: (12)

42: (2,2,2) 2080: (6,6)

63: (1,1,1,1,1,1) 2184: (4,4,4)

64: (7) 2340: (3,3,3,3)

127: (1,1,1,1,1,1,1) 2730: (2,2,2,2,2,2)

128: (8) 4095: (1,1,1,1,1,1,1,1,1,1,1,1)

(End)

The standard order of compositions is given by A066099.

For n > 0, a(n) is one more than the number of adjacent unequal terms in the n-th composition in standard order. Also the number of runs in the same composition. - Gus Wiseman, Apr 08 2020

Deutsch shows in his 1999 paper that this automorphism maps the number of doublerises of Dyck paths to number of valleys and height of the first peak to the number of returns, i.e., that A126306(n) = A127284(a(n)) and A126307(n) = A057515(a(n)) hold for all n.

The A000108(n-2) n-gon triangularizations can be reflected over n axes of symmetry, which all can be generated by appropriate compositions of the permutations A057161/A057162 and A057163.

Composition with A057164 gives signature permutation for Donaghey's Map M (A057505/A057506). Embeds into itself in scale n:2n+1 as a(n) = A083928(a(A080298(n))). A127302(a(n)) = A127302(n) and A057123(A057163(n)) = A057164(A057123(n)) hold for all n.

Number of terms in interval [2^(n-1), 2^n) is the number of compositions of n with distinct parts (cf. A032020). For example, if n=6, then interval [2^5, 2^6) contains 11 terms {32,...,52}. This corresponds to 11 compositions with distinct parts of 6: 6, 5+1, 1+5, 4+2, 2+4, 3+2+1, 3+1+2, 2+3+1, 2+1+3, 1+3+2, 1+2+3.

From Gus Wiseman, Apr 06 2020: (Start)

The k-th composition in standard order (row k of A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions. This sequence lists all numbers k such that the k-th composition in standard order is strict. For example, the sequence together with the corresponding strict compositions begins:

0: () 38: (3,1,2) 98: (1,4,2)

1: (1) 40: (2,4) 104: (1,2,4)

2: (2) 41: (2,3,1) 128: (8)

4: (3) 44: (2,1,3) 129: (7,1)

5: (2,1) 48: (1,5) 130: (6,2)

6: (1,2) 50: (1,3,2) 132: (5,3)

8: (4) 52: (1,2,3) 133: (5,2,1)

9: (3,1) 64: (7) 134: (5,1,2)

12: (1,3) 65: (6,1) 137: (4,3,1)

16: (5) 66: (5,2) 140: (4,1,3)

17: (4,1) 68: (4,3) 144: (3,5)

18: (3,2) 69: (4,2,1) 145: (3,4,1)

20: (2,3) 70: (4,1,2) 152: (3,1,4)

24: (1,4) 72: (3,4) 160: (2,6)

32: (6) 80: (2,5) 161: (2,5,1)

33: (5,1) 81: (2,4,1) 176: (2,1,5)

34: (4,2) 88: (2,1,4) 192: (1,7)

37: (3,2,1) 96: (1,6) 194: (1,5,2)

(End)

The k-th composition in standard order (row k of A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again.

First differences of A000123; also A000123 with terms repeated. See the relevant proof that follows the first formula below.

Among these partitions there is exactly one partition with all distinct terms, as every number can be expressed as the sum of the distinct powers of 2.

Euler transform of A036987 with offset 1.

a(n) is the number of "non-squashing" partitions of n, that is, partitions n = p_1 + p_2 + ... + p_k with 1 <= p_1 <= p_2 <= ... <= p_k and p_1 + p_2 + ... + p_i <= p_{i+1} for all 1 <= i < k. - N. J. A. Sloane, Nov 30 2003

Normally the OEIS does not include sequences like this where every term is repeated, but an exception was made for this one because of its importance. The unrepeated sequence A000123 is the main entry.

Number of different partial sums from 1 + [1, *2] + [1, *2] + ..., where [1, *2] means we can either add 1 or multiply by 2. E.g., a(6) = 6 because we have 6 = 1 + 1 + 1 + 1 + 1 + 1 = (1+1) * 2 + 1 + 1 = 1 * 2 * 2 + 1 + 1 = (1+1+1) * 2 = 1 * 2 + 1 + 1 + 1 + 1 = (1*2+1) * 2 where the connection is defined via expanding each bracket; e.g., this is 6 = 1 + 1 + 1 + 1 + 1 + 1 = 2 + 2 + 1 + 1 = 4 + 1 + 1 = 2 + 2 + 2 = 2 + 1 + 1 + 1 + 1 = 4 + 2. - Jon Perry, Jan 01 2004

Number of partitions p of n such that the number of compositions generated by p is odd. For proof see the Alekseyev and Adams-Watters link. - Vladeta Jovovic, Aug 06 2007

Differs from A008645 first at a(64). - R. J. Mathar, May 28 2008

Appears to be row sums of A155077. - Mats Granvik, Jan 19 2009

Number of partitions (p_1, p_2, ..., p_k) of n, with p_1 >= p_2 >= ... >= p_k, such that for each i, p_i >= p_{i+1} + ... + p_k. - John MCKAY (mckay(AT)encs.concordia.ca), Mar 06 2009 (these are the "non-squashing" partitions as nonincreasing lists).

Equals rightmost diagonal of triangle of A168261. Starting with offset 1 = eigensequence of triangle A115361 and row sums of triangle A168261. - Gary W. Adamson, Nov 21 2009

Equals convolution square root of A171238: (1, 2, 5, 8, 16, 24, 40, 56, 88, ...). - Gary W. Adamson, Dec 05 2009

Let B = the n-th convolution power of the sequence and C = the aerated variant of B. It appears that B/C = the binomial sequence beginning (1, n, ...). Example: Third convolution power of the sequence is (1, 3, 9, 19, 42, 78, 146, ...), with C = (1, 0, 3, 0, 9, 0, 19, ...). Then B/C = (1, 3, 6, 10, 15, 21, ...). - Gary W. Adamson, Aug 15 2016

From Gary W. Adamson, Sep 08 2016: (Start)

The limit of the matrix power M^k as n-->inf results in a single column vector equal to the sequence, where M is the following production matrix:

1, 0, 0, 0, 0, ...

1, 0, 0, 0, 0, ...

1, 1, 0, 0, 0, ...

1, 1, 0, 0, 0, ...

1, 1, 1, 0, 0, ...

1, 1, 1, 0, 0, ...

1, 1, 1, 1, 0, ...

1, 1, 1, 1, 0, ...

1, 1, 1, 1, 1, ...

... (End)

a(n) is the number of "non-borrowing" partitions of n, meaning binary subtraction of a smaller part from a larger part will never require place-value borrowing. - David V. Feldman, Jan 29 2020

From Gus Wiseman, May 25 2024: (Start)

Also the number of multisets of positive integers whose binary rank is n, where the binary rank of a multiset m is given by Sum_i 2^(m_i-1). For example, the a(1) = 1 through a(8) = 10 multisets are:

{1} {2} {12} {3} {13} {23} {123} {4}

{11} {111} {22} {122} {113} {1113} {33}

{112} {1112} {222} {1222} {223}

{1111} {11111} {1122} {11122} {1123}

{11112} {111112} {2222}

{111111} {1111111} {11113}

{11222}

{111122}

{1111112}

{11111111}

(End)

A binary index of n is any position of a 1 in its reversed binary expansion. We define the set-system with BII-number n to be obtained by taking the binary indices of each binary index of n. Every finite set of finite nonempty sets of positive integers has a different BII-number. For example, 18 has reversed binary expansion (0,1,0,0,1), and since the binary indices of 2 and 5 are {2} and {1,3} respectively, it follows that the BII-number of {{2},{1,3}} is 18. The weight of a set-system is the sum of sizes of its elements (sometimes called its edges).

The representation of the compositions (for fixed n) is as lists of parts, the order between individual compositions (for the same n) is (list-)reversed co-lexicographic. - Joerg Arndt, Sep 02 2013

Dropping the "(list-)reversed" in the comment above gives A228525.

The equivalent sequence for partitions is A026792.

This sequence lists (without repetitions) all finite compositions, in such a way that, if [P_1, ..., P_r] denotes the composition occupying the n-th position in the list, then (((2*n/2^(P_1)-1)/2^(P_2)-1)/...)/2^(P_r)-1 = 0. - Lorenzo Sauras Altuzarra, Jan 22 2020

The k-th composition in the list is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, and taking first differences. Reversing again gives A066099, which is described as the standard ordering. Both sequences define a bijective correspondence between nonnegative integers and integer compositions. - Gus Wiseman, Apr 01 2020

It follows from the previous comment that A000120(k) is the length of the k-th composition that is listed by this sequence (recall that A000120(k) is the number of 1's in the binary expansion of k). - Lorenzo Sauras Altuzarra, Sep 29 2020

Anti-runs are sequences without any adjacent equal terms.

A composition of n is a finite sequence of positive integers summing to n. The k-th composition in standard order (row k of A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again.

For n > 0, also one plus the number of adjacent equal pairs in the n-th composition in standard order.