login
Numbers k such that the k-th composition in standard order is not the sequence of run-sums of any other composition.
6

%I #8 Jun 22 2022 09:27:23

%S 3,7,11,14,15,19,23,27,28,29,30,31,35,39,43,46,47,51,53,55,56,57,58,

%T 59,60,61,62,63,67,71,75,78,79,83,87,91,92,93,94,95,99,103,107,110,

%U 111,112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127

%N Numbers k such that the k-th composition in standard order is not the sequence of run-sums of any other composition.

%C 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.

%C Every sequence can be uniquely split into a sequence of non-overlapping runs. 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).

%C The first term k such that the k-th composition in standard order does not have ones sandwiching the same prime number an even number of times is k = 3221, corresponding to the composition (1,3,3,2,2,1).

%e The terms and their corresponding compositions begin:

%e 3: (1,1)

%e 7: (1,1,1)

%e 11: (2,1,1)

%e 14: (1,1,2)

%e 15: (1,1,1,1)

%e 19: (3,1,1)

%e 23: (2,1,1,1)

%e 27: (1,2,1,1)

%e 28: (1,1,3)

%e 29: (1,1,2,1)

%e 30: (1,1,1,2)

%e 31: (1,1,1,1,1)

%t stc[n_]:=Differences[Prepend[Join@@ Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;

%t Select[Range[0,100],FreeQ[Total/@Split[#]&/@ Join@@Permutations/@IntegerPartitions[Total[stc[#]]],stc[#]]&]

%Y The standard compositions used here are A066099, run-sums A353847/A353932.

%Y These are the positions of zeros in A354578, firsts A354905.

%Y These compositions are counted by A354909.

%Y The complement is A354912, counted by A354910.

%Y A003242 counts anti-run compositions, ranked by A333489.

%Y A124767 counts runs in standard compositions.

%Y A238279 and A333755 count compositions by number of runs.

%Y A351014 counts distinct runs of standard compositions, firsts A351015.

%Y A353852 ranks compositions with distinct run-sums, counted by A353850.

%Y A353853-A353859 pertain to composition run-sum trajectory.

%Y Cf. A000120, A000918, A005811, A029837, A333381, A334299, A353832, A353849, A353860, A354907.

%K nonn

%O 1,1

%A _Gus Wiseman_, Jun 21 2022