login
A373953
Sum of run-compression of the n-th integer composition in standard order.
46
0, 1, 2, 1, 3, 3, 3, 1, 4, 4, 2, 3, 4, 4, 3, 1, 5, 5, 5, 4, 5, 3, 5, 3, 5, 5, 3, 4, 4, 4, 3, 1, 6, 6, 6, 5, 3, 6, 6, 4, 6, 6, 2, 3, 6, 6, 5, 3, 6, 6, 6, 5, 6, 4, 6, 4, 5, 5, 3, 4, 4, 4, 3, 1, 7, 7, 7, 6, 7, 7, 7, 5, 7, 4, 5, 6, 7, 7, 6, 4, 7, 7, 7, 6, 5, 3, 5
OFFSET
0,3
COMMENTS
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.
We define the (run-) compression of a sequence to be the anti-run obtained by reducing each run of repeated parts to a single part. Alternatively, compression removes all parts equal to the part immediately to their left. For example, (1,1,2,2,1) has compression (1,2,1).
FORMULA
a(n) = A029837(A373948(n)).
EXAMPLE
The standard compositions and their compressions and compression sums begin:
0: () --> () --> 0
1: (1) --> (1) --> 1
2: (2) --> (2) --> 2
3: (1,1) --> (1) --> 1
4: (3) --> (3) --> 3
5: (2,1) --> (2,1) --> 3
6: (1,2) --> (1,2) --> 3
7: (1,1,1) --> (1) --> 1
8: (4) --> (4) --> 4
9: (3,1) --> (3,1) --> 4
10: (2,2) --> (2) --> 2
11: (2,1,1) --> (2,1) --> 3
12: (1,3) --> (1,3) --> 4
13: (1,2,1) --> (1,2,1) --> 4
14: (1,1,2) --> (1,2) --> 3
15: (1,1,1,1) --> (1) --> 1
MATHEMATICA
stc[n_]:=Differences[Prepend[Join @@ Position[Reverse[IntegerDigits[n, 2]], 1], 0]]//Reverse;
Table[Total[First/@Split[stc[n]]], {n, 0, 100}]
CROSSREFS
Positions of 1's are A000225.
Counting partitions by this statistic gives A116861, by length A116608.
For length instead of sum we have A124767, counted by A238279 and A333755.
Compositions counted by this statistic are A373949, opposite A373951.
A037201 gives compression of first differences of primes, halved A373947.
A066099 lists the parts of all compositions in standard order.
A114901 counts compositions with no isolated parts.
A240085 counts compositions with no unique parts.
A333489 ranks anti-runs, counted by A003242.
Sequence in context: A099246 A303119 A039775 * A302291 A300510 A361079
KEYWORD
nonn
AUTHOR
Gus Wiseman, Jun 25 2024
STATUS
approved