A353431 Numbers k such that the k-th composition in standard order is empty, a singleton, or has its own run-lengths as a subsequence (not necessarily consecutive) that is already counted.

0, 1, 2, 4, 8, 10, 16, 32, 43, 58, 64, 128, 256, 292, 349, 442, 512, 586, 676, 697, 826, 1024, 1210, 1338, 1393, 1394, 1396, 1594, 2048, 2186, 2234, 2618, 2696, 2785, 2786, 2792, 3130, 4096, 4282, 4410, 4666, 5178, 5569, 5570, 5572, 5576, 5584, 6202, 8192

Offset

1,3

Comments

First differs from A353696 (the consecutive version) in having 22318, corresponding to the binary word 101011100101110 and standard composition (2,2,1,1,3,2,1,1,2), whose run-lengths (2,2,1,1,2,1) are subsequence but not a consecutive subsequence.

The k-th composition in standard order (graded reverse-lexicographic, 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.

Links

Table of n, a(n) for n=1..49.

Example

The initial terms, their binary expansions, and the corresponding standard compositions:
     0:           0  ()
     1:           1  (1)
     2:          10  (2)
     4:         100  (3)
     8:        1000  (4)
    10:        1010  (2,2)
    16:       10000  (5)
    32:      100000  (6)
    43:      101011  (2,2,1,1)
    58:      111010  (1,1,2,2)
    64:     1000000  (7)
   128:    10000000  (8)
   256:   100000000  (9)
   292:   100100100  (3,3,3)
   349:   101011101  (2,2,1,1,2,1)
   442:   110111010  (1,2,1,1,2,2)
   512:  1000000000  (10)
   586:  1001001010  (3,3,2,2)
   676:  1010100100  (2,2,3,3)
   697:  1010111001  (2,2,1,1,3,1)

Mathematica

stc[n_]:=Differences[Prepend[Join@@ Position[Reverse[IntegerDigits[n, 2]], 1], 0]]//Reverse;
rorQ[y_]:=Length[y]<=1||MemberQ[Subsets[y], Length/@Split[y]]&& rorQ[Length/@Split[y]];
Select[Range[0, 100], rorQ[stc[#]]&]

Crossrefs

The non-recursive version for partitions is A325755, counted by A325702.

These compositions are counted by A353391.

The version for partitions A353393, counted by A353426, w/o primes A353389.

The non-recursive version is A353402, counted by A353390.

The non-recursive consecutive case is A353432, counted by A353392.

The consecutive case is A353696, counted by A353430.

A005811 counts runs in binary expansion.

A011782 counts compositions.

A066099 lists compositions in standard order, rev A228351, run-lens A333769.

A329738 counts uniform compositions, partitions A047966.

Statistics of standard compositions:

- Length is A000120, sum A070939.

- Runs are counted by A124767, distinct A351014.

- Subsequences are counted by A334299, contiguous A124770/A124771.

- Runs-resistance is A333628.

Classes of standard compositions:

- Partitions are A114994, multisets A225620, strict A333255, sets A333256.

- Constant compositions are A272919, counted by A000005.

- Golomb rulers are A333222, counted by A169942.

- Knapsack compositions are A333223, counted by A325676.

- Anti-runs are A333489, counted by A003242.

Cf. A032020, A044813, A114640, A165413, A181819, A329739, A318928, A325705, A333224, A353427, A353403.

Sequence in context: A291165 A083655 A335404 * A353696 A271816 A097210

Adjacent sequences: A353428 A353429 A353430 * A353432 A353433 A353434

Keyword

nonn

Author

Gus Wiseman, May 16 2022

Status

approved