cp's OEIS Frontend

A354581 Numbers k such that the k-th composition in standard order is rucksack, meaning every distinct partial run has a different sum.

%I A354581 #8 Jun 17 2022 08:35:06
%S A354581 0,1,2,3,4,5,6,7,8,9,10,12,13,15,16,17,18,19,20,21,22,24,25,26,28,31,
%T A354581 32,33,34,35,36,37,38,40,41,42,44,45,48,49,50,51,52,53,54,56,57,63,64,
%U A354581 65,66,67,68,69,70,71,72,73,74,76,77,80,81,82,84,85,86,88
%N A354581 Numbers k such that the k-th composition in standard order is rucksack, meaning every distinct partial run has a different sum.
%C A354581 We define a partial run of a sequence to be any contiguous constant subsequence.
%C A354581 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 A354581 The term rucksack is short for run-knapsack.
%e A354581 The terms together with their corresponding compositions begin:
%e A354581    0: ()
%e A354581    1: (1)
%e A354581    2: (2)
%e A354581    3: (1,1)
%e A354581    4: (3)
%e A354581    5: (2,1)
%e A354581    6: (1,2)
%e A354581    7: (1,1,1)
%e A354581    8: (4)
%e A354581    9: (3,1)
%e A354581   10: (2,2)
%e A354581   12: (1,3)
%e A354581   13: (1,2,1)
%e A354581   15: (1,1,1,1)
%e A354581 Missing are:
%e A354581   11: (2,1,1)
%e A354581   14: (1,1,2)
%e A354581   23: (2,1,1,1)
%e A354581   27: (1,2,1,1)
%e A354581   29: (1,1,2,1)
%e A354581   30: (1,1,1,2)
%e A354581   39: (3,1,1,1)
%e A354581   43: (2,2,1,1)
%e A354581   46: (2,1,1,2)
%t A354581 stc[n_]:=Differences[Prepend[Join@@ Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
%t A354581 Select[Range[0,100],UnsameQ@@Total/@Union@@Subsets/@Split[stc[#]]&]
%Y A354581 The version for binary indices is A000225.
%Y A354581 Counting distinct sums of full runs gives A353849, partitions A353835.
%Y A354581 For partitions we have A353866, counted by A353864, complement A354583.
%Y A354581 These compositions are counted by A354580.
%Y A354581 Counting distinct sums of partial runs gives A354907, partitions A353861.
%Y A354581 A066099 lists all compositions in standard order.
%Y A354581 A124767 counts runs in standard compositions.
%Y A354581 A124771 counts distinct contiguous subsequences, non-contiguous A334299.
%Y A354581 A238279 and A333755 count compositions by number of runs.
%Y A354581 A351014 counts distinct runs in standard compositions, firsts A351015.
%Y A354581 A353838 ranks partitions with all distinct run-sums, counted by A353837.
%Y A354581 A353851 counts compositions with all equal run-sums, ranked by A353848.
%Y A354581 A353852 ranks compositions with all distinct run-sums, counted by A353850.
%Y A354581 A353853-A353859 pertain to composition run-sum trajectory.
%Y A354581 A353932 lists run-sums of standard compositions, rows ranked by A353847.
%Y A354581 Cf. A000120, A005811, A029837, A063787, A175413, A181819, A330036, A333381, A333489, A353832, A353860.
%K A354581 nonn
%O A354581 0,3
%A A354581 _Gus Wiseman_, Jun 15 2022