A353851 -id:A353851 - 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.

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, 32, 33, 34, 35, 36, 37, 38, 40, 41, 42, 44, 45, 48, 49, 50, 51, 52, 53, 54, 56, 57, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 76, 77, 80, 81, 82, 84, 85, 86, 88

Offset: 0

Gus Wiseman, Jun 15 2022

nonn

We define a partial run of a sequence to be any contiguous constant 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.
The term rucksack is short for run-knapsack.

			The terms together with their corresponding compositions begin:
   0: ()
   1: (1)
   2: (2)
   3: (1,1)
   4: (3)
   5: (2,1)
   6: (1,2)
   7: (1,1,1)
   8: (4)
   9: (3,1)
  10: (2,2)
  12: (1,3)
  13: (1,2,1)
  15: (1,1,1,1)
Missing are:
  11: (2,1,1)
  14: (1,1,2)
  23: (2,1,1,1)
  27: (1,2,1,1)
  29: (1,1,2,1)
  30: (1,1,1,2)
  39: (3,1,1,1)
  43: (2,2,1,1)
  46: (2,1,1,2)

The version for binary indices is A000225.
Counting distinct sums of full runs gives A353849, partitions A353835.
For partitions we have A353866, counted by A353864, complement A354583.
These compositions are counted by A354580.
Counting distinct sums of partial runs gives A354907, partitions A353861.
A066099 lists all compositions in standard order.
A124767 counts runs in standard compositions.
A124771 counts distinct contiguous subsequences, non-contiguous A334299.
A238279 and A333755 count compositions by number of runs.
A351014 counts distinct runs in standard compositions, firsts A351015.
A353838 ranks partitions with all distinct run-sums, counted by A353837.
A353851 counts compositions with all equal run-sums, ranked by A353848.
A353852 ranks compositions with all distinct run-sums, counted by A353850.
A353853-A353859 pertain to composition run-sum trajectory.
A353932 lists run-sums of standard compositions, rows ranked by A353847.
Cf. A000120, A005811, A029837, A063787, A175413, A181819, A330036, A333381, A333489, A353832, A353860.

stc[n_]:=Differences[Prepend[Join@@ Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
Select[Range[0,100],UnsameQ@@Total/@Union@@Subsets/@Split[stc[#]]&]

A354579 Number of distinct lengths of runs in the n-th composition in standard order.

Original entry on oeis.org

0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 1, 2, 2, 2, 2, 2, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 2, 1, 2, 1, 2, 2, 2, 1, 2, 2, 2, 2, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 2, 2, 2, 1, 1, 2, 2, 1, 1, 1, 2, 2, 2, 2

Offset: 0

Gus Wiseman, Jun 11 2022

nonn

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 lengths (2,3,1,2).

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.

			The positions of first appearances together with the corresponding compositions begin:
       1: (1)
      11: (2,1,1)
     119: (1,1,2,1,1,1)
    5615: (2,2,1,1,1,2,1,1,1,1)
  251871: (1,1,1,2,2,1,1,1,1,2,1,1,1,1,1)

Standard compositions are listed by A066099.
The version for partitions is A071625.
For runs instead of run-lengths we have A351014, firsts A351015.
Positions of 0's and 1's are A353744, counted by A329738.
For sums instead of lengths we have A353849, ones at A353848.
Positions of first appearances are A354906.
A003242 counts anti-run compositions, ranked by A333489.
A005811 counts runs in binary expansion.
A333627 ranks the run-lengths of standard compositions.
A351596 ranks compositions with distinct run-lengths, counted by A329739.
A353835 counts distinct run-sums of prime indices, weak A353861.
A353847 ranks the run-sums of standard compositions.
A353852 ranks compositions with distinct run-sums, counted by A353850.
A353860 counts collapsible compositions.
Cf. A029837, A124767, A181819, A238279, A333381, A333755, A353839, A353851.

stc[n_]:=Differences[Prepend[Join@@ Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
Table[Length[Union[Length/@Split[stc[n]]]],{n,0,100}]

A354909 Number of integer compositions of n that are not the run-sums of any other composition.

Original entry on oeis.org

0, 0, 1, 1, 3, 7, 16, 33, 74, 155, 329, 688, 1439, 2975, 6154, 12654, 25964, 53091, 108369, 220643, 448520

Offset: 0

Gus Wiseman, Jun 19 2022

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).

			The a(0) = 0 through a(6) = 16 compositions:
  .  .  (11)  (111)  (112)   (113)    (114)
                     (211)   (311)    (411)
                     (1111)  (1112)   (1113)
                             (1121)   (1122)
                             (1211)   (1131)
                             (2111)   (1221)
                             (11111)  (1311)
                                      (2112)
                                      (2211)
                                      (3111)
                                      (11112)
                                      (11121)
                                      (11211)
                                      (12111)
                                      (21111)
                                      (111111)

The version for binary words is A000918, complement A000126.
These compositions are ranked by A354904 = positions of zeros in A354578.
The complement is counted by A354910, ranked by A354912.
A003242 counts anti-run compositions, ranked by A333489.
A238279 and A333755 count compositions by number of runs.
A353851 counts compositions with all equal run-sums, ranked by A353848.
A353853-A353859 pertain to composition run-sum trajectory.
A353932 lists run-sums of standard compositions, rows ranked by A353847.
Cf. A005811, A027336, A066099, A124767, A274174, A351597, A353849, A353850, A353860, A354905, A354907.

Table[Length[Complement[Join@@Permutations/@IntegerPartitions[n], Total/@Split[#]&/@Join@@Permutations/@IntegerPartitions[n]]],{n,0,15}]

A354910 Number of compositions of n that are the run-sums of some other composition.

Original entry on oeis.org

1, 1, 1, 3, 5, 9, 16, 31, 54, 101, 183, 336, 609, 1121, 2038, 3730, 6804, 12445, 22703, 41501, 75768

Offset: 0

Gus Wiseman, Jun 20 2022

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).

			The a(0) = 0 through a(6) = 16 compositions:
  ()  (1)  (2)  (3)   (4)    (5)    (6)
                (12)  (13)   (14)   (15)
                (21)  (22)   (23)   (24)
                      (31)   (32)   (33)
                      (121)  (41)   (42)
                             (122)  (51)
                             (131)  (123)
                             (212)  (132)
                             (221)  (141)
                                    (213)
                                    (222)
                                    (231)
                                    (312)
                                    (321)
                                    (1212)
                                    (2121)

The version for binary words is A000126, complement A000918
The complement is counted by A354909, ranked by A354904.
These compositions are ranked by A354912 = nonzeros of A354578.
A003242 counts anti-run compositions, ranked by A333489.
A238279 and A333755 count compositions by number of runs.
A353851 counts compositions with all equal run-sums, ranked by A353848.
A353853-A353859 pertain to composition run-sum trajectory.
A353932 lists run-sums of standard compositions, rows ranked by A353847.
Cf. A005811, A027336, A066099, A239312, A274174, A351014, A351597, A353849, A353850, A353864, A354905, A354907.

Table[Length[Union[Total/@Split[#]&/@ Join@@Permutations/@IntegerPartitions[n]]],{n,0,15}]

A383088 Numbers whose multiset of prime indices does not have all equal run-sums.

Original entry on oeis.org

6, 10, 14, 15, 18, 20, 21, 22, 24, 26, 28, 30, 33, 34, 35, 36, 38, 39, 42, 44, 45, 46, 48, 50, 51, 52, 54, 55, 56, 57, 58, 60, 62, 65, 66, 68, 69, 70, 72, 74, 75, 76, 77, 78, 80, 82, 84, 85, 86, 87, 88, 90, 91, 92, 93, 94, 95, 96, 98, 99, 100, 102, 104, 105

Offset: 1

Gus Wiseman, Apr 17 2025

nonn

First differs from A381871 in having 36.

A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798, sum A056239.

			The prime indices of 36 are {1,1,2,2}, with run-sums (2,4), so 36 is in the sequence, even though we have the multiset partition {{1,1},{2},{2}} with equal sums.
The terms together with their prime indices begin:
    6: {1,2}
   10: {1,3}
   14: {1,4}
   15: {2,3}
   18: {1,2,2}
   20: {1,1,3}
   21: {2,4}
   22: {1,5}
   24: {1,1,1,2}
   26: {1,6}
   28: {1,1,4}
   30: {1,2,3}
   33: {2,5}
   34: {1,7}
   35: {3,4}
   36: {1,1,2,2}
   38: {1,8}
   39: {2,6}
   42: {1,2,4}
   44: {1,1,5}
   45: {2,2,3}
   46: {1,9}

For run-lengths instead of sums we have A059404, distinct A130092.
The complement is A353833, counted by A304442.
For distinct instead of equal run-sums we have A353839.
Partitions of this type are counted by A382076.
Counting and ranking partitions by run-lengths and run-sums:
- constant: A047966 (ranks A072774), sums A304442 (ranks A353833)
- distinct: A098859 (ranks A130091), sums A353837 (ranks A353838)
- weakly decreasing: A100882 (ranks A242031), sums A304405 (ranks A357875)
- weakly increasing: A100883 (ranks A304678), sums A304406 (ranks A357861)
- strictly decreasing: A100881 (ranks A304686), sums A304428 (ranks A357862)
- strictly increasing: A100471 (ranks A334965), sums A304430 (ranks A357864)
A001222 counts prime factors, distinct A001221.
A056239 adds up prime indices, row sums of A112798.
A326534 ranks multiset partitions with a common sum, counted by A321455, normal A326518.
A353851 counts compositions with a common run-sum, ranks A353848.
A353862 gives the greatest run-sum of prime indices, least A353931.
A382877 counts permutations of prime indices with equal run-sums, zeros A383100.
A383098 counts partitions with a permutation having all equal run-sums, ranks A383110.
Cf. A000720, A006171, A300273, A353861, A353932, A354584, A383014, A383015, A383095, A383097, A383099.

Select[Range[100], !SameQ@@Cases[FactorInteger[#],{p_,k_}:>PrimePi[p]*k]&]

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.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A354579 Number of distinct lengths of runs in the n-th composition in standard order.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A354909 Number of integer compositions of n that are not the run-sums of any other composition.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A354910 Number of compositions of n that are the run-sums of some other composition.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A383088 Numbers whose multiset of prime indices does not have all equal run-sums.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica