OFFSET
0,3
COMMENTS
Every sequence can be uniquely split into non-overlapping runs, read left-to-right. For example, the runs of (2,2,1,1,1,3,2,2) are ((2,2),(1,1,1),(3),(2,2)), with sums (4,3,3,4).
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
Mathematics Stack Exchange, What is a sequence run? (answered 2011-12-01)
FORMULA
A353849(a(n)) = 1.
EXAMPLE
The terms together with their binary expansions and corresponding compositions begin:
0: 0 ()
1: 1 (1)
2: 10 (2)
3: 11 (1,1)
4: 100 (3)
7: 111 (1,1,1)
8: 1000 (4)
10: 1010 (2,2)
11: 1011 (2,1,1)
14: 1110 (1,1,2)
15: 1111 (1,1,1,1)
16: 10000 (5)
31: 11111 (1,1,1,1,1)
32: 100000 (6)
36: 100100 (3,3)
39: 100111 (3,1,1,1)
42: 101010 (2,2,2)
46: 101110 (2,1,1,2)
59: 111011 (1,1,2,1,1)
60: 111100 (1,1,1,3)
For example:
- The 59th composition in standard order is (1,1,2,1,1), with run-sums (2,2,2), so 59 is in the sequence.
- The 2298th composition in standard order is (4,1,1,1,1,2,2), with run-sums (4,4,4), so 2298 is in the sequence.
- The 2346th composition in standard order is (3,3,2,2,2), with run-sums (6,6), so 2346 is in the sequence.
MATHEMATICA
stc[n_]:=Differences[Prepend[Join@@ Position[Reverse[IntegerDigits[n, 2]], 1], 0]]//Reverse;
Select[Range[0, 100], SameQ@@Total/@Split[stc[#]]&]
CROSSREFS
Standard compositions are listed by A066099.
These compositions are counted by A353851.
A005811 counts runs in binary expansion.
A353847 represents the run-sum transformation for compositions.
A353860 counts collapsible compositions.
A353863 counts run-sum-complete partitions.
KEYWORD
nonn
AUTHOR
Gus Wiseman, May 30 2022
STATUS
approved