A329738 -id:A329738 - cp's OEIS frontend

A329866 Numbers whose binary expansion has its runs-resistance equal to its cuts-resistance minus 1.

1, 3, 16, 30, 33, 48, 55, 56, 59, 60, 67, 68, 72, 79, 95, 97, 110, 112, 118, 120, 121, 125, 134, 135, 137, 143, 145, 158, 160, 195, 196, 219, 220, 225, 231, 241, 250, 258, 270, 280, 286, 291, 292, 315, 316, 351, 381, 382, 390, 391, 393, 399, 415, 416, 431, 432

Offset: 1

Gus Wiseman, Nov 23 2019

nonn

For the operation of taking the sequence of run-lengths of a finite sequence, runs-resistance is defined to be the number of applications required to reach a singleton.

For the operation of shortening all runs by 1, cuts-resistance is defined to be the number of applications required to reach an empty word.

			The sequence of terms together with their binary expansions begins:
    1:         1
    3:        11
   16:     10000
   30:     11110
   33:    100001
   48:    110000
   55:    110111
   56:    111000
   59:    111011
   60:    111100
   67:   1000011
   68:   1000100
   72:   1001000
   79:   1001111
   95:   1011111
   97:   1100001
  110:   1101110
  112:   1110000
  118:   1110110
  120:   1111000
For example, 79 has runs-resistance 3 because we have (1001111) -> (124) -> (111) -> (3), while the cuts-resistance is 4 because we have (1001111) -> (0111) -> (11) -> (1) -> (), so 79 is in the sequence.

Claude Lenormand, Deux transformations sur les mots, Preprint, 5 pages, Nov 17 2003.

Positions of -1's in A329867.
The version for runs-resistance equal to cuts-resistance is A329865.
Compositions with runs-resistance equal to cuts-resistance are A329864.
Compositions with runs-resistance = cuts-resistance minus 1 are A329869.
Runs-resistance of binary expansion is A318928.
Cuts-resistance of binary expansion is A319416.
Compositions counted by runs-resistance are A329744.
Compositions counted by cuts-resistance are A329861.
Binary words counted by runs-resistance are A319411 and A329767.
Binary words counted by cuts-resistance are A319421 and A329860.
Cf. A000975, A003242, A107907, A164707, A329738, A329868.

runsres[q_]:=Length[NestWhileList[Length/@Split[#]&,q,Length[#]>1&]]-1;
degdep[q_]:=Length[NestWhileList[Join@@Rest/@Split[#]&,q,Length[#]>0&]]-1;
Select[Range[100],runsres[IntegerDigits[#,2]]-degdep[IntegerDigits[#,2]]==-1&]

A329868 Sorted positions of first appearances in A329867 (difference between the runs-resistance and the cuts-resistance of binary expansion) of each element in the image.

Original entry on oeis.org

0, 1, 2, 7, 11, 15, 18, 31, 63, 75, 127, 255, 511, 1023, 1234, 2047, 4095, 8191, 9638, 16383, 32767, 65535, 131071, 262143, 524287, 1048575, 2097151, 4194303, 8388607

Offset: 1

Gus Wiseman, Nov 23 2019

For the operation of taking the sequence of run-lengths of a finite sequence, runs-resistance is defined to be the number of applications required to reach a singleton.

For the operation of shortening all runs by 1, cuts-resistance is defined to be the number of applications required to reach an empty word.

			The sequence of terms together with their binary expansions begins:
      0:
      1:                1
      2:               10
      7:              111
     11:             1011
     15:             1111
     18:            10010
     31:            11111
     63:           111111
     75:          1001011
    127:          1111111
    255:         11111111
    511:        111111111
   1023:       1111111111
   1234:      10011010010
   2047:      11111111111
   4095:     111111111111
   8191:    1111111111111
   9638:   10010110100110
  16383:   11111111111111
  32767:  111111111111111
  65535: 1111111111111111

Claude Lenormand, Deux transformations sur les mots, Preprint, 5 pages, Nov 17 2003.

Sorted positions of first appearances in A329867.
Compositions with runs-resistance equal to cuts-resistance are A329864.
Runs-resistance of binary expansion is A318928.
Cuts-resistance of binary expansion is A319416.
Compositions counted by runs-resistance are A329744.
Compositions counted by cuts-resistance are A329861.
Binary words counted by runs-resistance are A319411 and A329767.
Binary words counted by cuts-resistance are A319421 and A329860.
Cf. A000975, A003242, A107907, A164707, A329738, A329865, A329866.

runsres[q_]:=Length[NestWhileList[Length/@Split[#]&,q,Length[#]>1&]]-1;
degdep[q_]:=Length[NestWhileList[Join@@Rest/@Split[#]&,q,Length[#]>0&]]-1;
das=Table[If[n==0,0,runsres[IntegerDigits[n,2]]-degdep[IntegerDigits[n,2]]],{n,0,1000000}];
Table[Position[das,i][[1,1]]-1,{i,First/@Gather[das]}]

A333192 Number of compositions of n with strictly increasing run-lengths.

Original entry on oeis.org

1, 1, 2, 2, 4, 5, 7, 10, 14, 16, 24, 31, 37, 51, 67, 76, 103, 129, 158, 199, 242, 293, 370, 450, 538, 652, 799, 953, 1147, 1376, 1635, 1956, 2322, 2757, 3271, 3845, 4539, 5336, 6282, 7366, 8589, 10046, 11735, 13647, 15858, 18442, 21354, 24716, 28630, 32985

Offset: 0

Gus Wiseman, May 17 2020

nonn

A composition of n is a finite sequence of positive integers summing to n.

			The a(1) = 1 through a(8) = 14 compositions:
  (1)  (2)   (3)    (4)     (5)      (6)       (7)        (8)
       (11)  (111)  (22)    (122)    (33)      (133)      (44)
                    (211)   (311)    (222)     (322)      (233)
                    (1111)  (2111)   (411)     (511)      (422)
                            (11111)  (3111)    (1222)     (611)
                                     (21111)   (4111)     (2222)
                                     (111111)  (22111)    (5111)
                                               (31111)    (11222)
                                               (211111)   (41111)
                                               (1111111)  (122111)
                                                          (221111)
                                                          (311111)
                                                          (2111111)
                                                          (11111111)
For example, the composition (1,2,2,1,1,1) has run-lengths (1,2,3), so is counted under a(8).

Giovanni Resta, Table of n, a(n) for n = 0..1000

The case of partitions is A100471.
The non-strict version is A332836.
Strictly increasing compositions are A000009.
Unimodal compositions are A001523.
Strict compositions are A032020.
Partitions with strictly increasing run-lengths are A100471.
Partitions with strictly decreasing run-lengths are A100881.
Compositions with equal run-lengths are A329738.
Compositions whose run-lengths are unimodal are A332726.
Compositions with strictly increasing or decreasing run-lengths are A333191.
Numbers with strictly increasing prime multiplicities are A334965.
Cf. A072706, A098859, A100882, A100883, A304686, A329744, A329766, A332726, A332833, A332834, A332835, A333147, A333149, A333190.

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],Less@@Length/@Split[#]&]],{n,0,15}]
b[n_, lst_, v_] := b[n, lst, v] = If[n == 0, 1, If[n <= lst, 0, Sum[If[k == v, 0, b[n - k pz, pz, k]], {pz, lst + 1, n}, {k, Floor[n/pz]}]]]; a[n_] := b[n, 0, 0]; a /@ Range[0, 50] (* Giovanni Resta, May 18 2020 *)

Terms a(26) and beyond from Giovanni Resta, May 18 2020

A353429 Number of integer compositions of n with all prime parts and all prime run-lengths.

Original entry on oeis.org

1, 0, 0, 0, 1, 0, 2, 0, 0, 1, 4, 0, 2, 2, 5, 4, 9, 1, 5, 12, 20, 11, 19, 18, 31, 43, 54, 37, 63, 95, 121, 124, 154, 178, 261, 353, 393, 417, 565, 770, 952, 1138, 1326, 1647, 2186, 2824, 3261, 3917, 4941, 6423, 7935, 9719, 11554, 14557, 18536, 23380, 27985

Offset: 0

Gus Wiseman, May 16 2022

nonn

			The a(13) = 2 through a(16) = 9 compositions:
  (22333)  (77)       (555)     (3355)
  (33322)  (2255)     (33333)   (5533)
           (5522)     (222333)  (22255)
           (223322)   (333222)  (55222)
           (2222222)            (332233)
                                (2222233)
                                (2223322)
                                (2233222)
                                (3322222)

Alois P. Heinz, Table of n, a(n) for n = 0..4000

The first condition only is A023360, partitions A000607.
For partitions we have A351982, only run-lens A100405, only parts A008483.
The second condition only is A353401, partitions A055923.
A003242 counts anti-run compositions, ranked by A333489.
A011782 counts compositions.
A052284 counts compositions into nonprimes, partitions A002095.
A106356 counts compositions by number of adjacent equal parts.
A114901 counts compositions with no runs of length 1, ranked by A353427.
A329738 counts uniform compositions, partitions A047966.
Cf. A005811, A128695, A137200, A167606, A333755, A335464, A353428.

b:= proc(n, h) option remember; `if`(n=0, 1, add(`if`(i<>h and isprime(i),
      add(`if`(isprime(j), b(n-i*j, i), 0), j=2..n/i), 0), i=2..n/2))
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..70);  # Alois P. Heinz, May 18 2022

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], And@@PrimeQ/@#&&And@@PrimeQ/@Length/@Split[#]&]],{n,0,15}]

a(26)-a(56) from Alois P. Heinz, May 18 2022

A382774 Number of ways to permute the prime indices of n! so that the run-lengths are all different.

Original entry on oeis.org

1, 1, 1, 0, 2, 0, 6, 0, 0, 0, 96, 0

Offset: 0

Gus Wiseman, Apr 09 2025

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 24 are {1,1,1,2}, with permutations (1,1,1,2) and (2,1,1,1), so a(4) = 2.

For anti-run permutations we have A335407, see also A335125, A382858.
This is the restriction of A382771 to the factorials A000142, equal A382857.
A022559 counts prime indices of n!, sum A081401.
A044813 lists numbers whose binary expansion has distinct run-lengths, equal A140690.
A056239 adds up prime indices, row sums of A112798.
A098859 counts partitions with distinct multiplicities, ordered A242882.
A239455 counts Look-and-Say partitions, ranks A351294, conjugate A381432.
A328592 lists numbers whose binary form has distinct runs of ones, equal A164707.
A329738 counts compositions with equal run-lengths, ranks A353744.
A329739 counts compositions with distinct run-lengths, ranks A351596.
A351293 counts non-Look-and-Say partitions, ranks A351295, conjugate A381433.
Cf. A000720, A001221, A001222, A003242, A048767, A130091, A181821, A351013, A351202, A360015, A382773, A382879.

Table[Length[Select[Permutations[prix[n!]],UnsameQ@@Length/@Split[#]&]],{n,0,6}]

a(n) = A382771(n!).

A383111 Number of integer partitions of n having more than one permutation with all distinct run-lengths.

Original entry on oeis.org

0, 0, 0, 0, 1, 3, 3, 8, 9, 13, 17, 26, 27, 43, 51, 61, 78, 103, 115, 153, 174, 213, 255, 316, 354, 442, 508, 610, 701, 848, 950, 1153, 1303, 1539, 1750, 2075, 2318, 2738, 3081

Offset: 0

Gus Wiseman, Apr 20 2025

			The partition (2,1,1) has two permutations with all distinct run-lengths: (1,1,2), (2,1,1), so it is counted under a(4).
The a(4) = 1 through a(9) = 13 partitions:
  (211)  (221)   (411)    (322)     (332)      (441)
         (311)   (3111)   (331)     (422)      (522)
         (2111)  (21111)  (511)     (611)      (711)
                          (2221)    (5111)     (3222)
                          (4111)    (22211)    (6111)
                          (22111)   (41111)    (22221)
                          (31111)   (221111)   (33111)
                          (211111)  (311111)   (51111)
                                    (2111111)  (222111)
                                               (411111)
                                               (2211111)
                                               (3111111)
                                               (21111111)

For a unique choice we have A000005, ranks A000961.
For at least one choice we have A239455, ranks A351294, conjugate A381432.
For no choices we have A351293, ranks A351295, conjugate A381433.
The complement is A351293 + A000005, ranks too dense.
For equal instead of distinct run-lengths we have A383090, ranks A383089.
These partitions are ranked by A383113 = positions of terms > 1 in A382771.
Cf. A047966, A098859, A130091, A353837, A100471, A100881, A100882, A100883
A000041 counts integer partitions, strict A000009.
A008284 counts partitions by length, strict A008289.
A329738 counts compositions with equal run-lengths, ranks A353744.
Cf. A047993, A329739, A381541, A381636, A381717, A382857, A382915, A383013, A383092, A383094, A383097.

Table[Length[Select[IntegerPartitions[n], Length[Select[Permutations[#], UnsameQ@@Length/@Split[#]&]]>1&]],{n,0,15}]

a(21)-a(38) from Jakub Buczak, May 04 2025

A329749 Number of complete compositions of n whose run-lengths cover an initial interval of positive integers.

Original entry on oeis.org

1, 1, 0, 2, 3, 5, 11, 23, 40, 80, 180, 344, 661, 1321, 2657, 5268, 10481, 20903, 41572, 82734, 164998, 328304, 654510, 1305421, 2598811, 5182174, 10332978, 20594318, 41066611, 81897091, 163309679, 325707492, 649648912, 1295827380, 2584941276, 5156774487

Offset: 0

Gus Wiseman, Nov 21 2019

nonn

A composition of n is a finite sequence of positive integers with sum n. It is complete if it covers an initial interval of positive integers.

			The a(0) = 1 through a(6) = 11 compositions (empty column not shown):
  ()  (1)  (1,2)  (1,1,2)  (1,2,2)    (1,2,3)
           (2,1)  (1,2,1)  (2,1,2)    (1,3,2)
                  (2,1,1)  (2,2,1)    (2,1,3)
                           (1,1,2,1)  (2,3,1)
                           (1,2,1,1)  (3,1,2)
                                      (3,2,1)
                                      (1,2,1,2)
                                      (1,2,2,1)
                                      (2,1,1,2)
                                      (2,1,2,1)
                                      (1,1,2,1,1)

Looking at  multiplicities instead of run-lengths gives A329748.
The non-complete version is A329766.
Complete compositions are A107429.
Cf. A000740, A008965, A098504, A244164, A274174, A329738, A329739, A329740, A329741, A329744.

normQ[m_]:=Or[m=={},Union[m]==Range[Max[m]]];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],normQ[#]&&normQ[Length/@Split[#]]&]],{n,0,10}]

a(21)-a(35) from Alois P. Heinz, Jul 06 2020

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}]

A332871 Number of compositions of n whose run-lengths are not weakly increasing.

Original entry on oeis.org

0, 0, 0, 0, 1, 4, 8, 24, 55, 128, 282, 625, 1336, 2855, 6000, 12551, 26022, 53744, 110361, 225914, 460756, 937413, 1902370, 3853445, 7791647, 15732468, 31725191, 63907437, 128613224, 258626480, 519700800, 1043690354, 2094882574, 4202903667, 8428794336, 16897836060

Offset: 0

Gus Wiseman, Feb 29 2020

nonn

A composition of n is a finite sequence of positive integers summing to n.

Also compositions whose run-lengths are not weakly decreasing.

			The a(4) = 1 through a(6) = 8 compositions:
  (112)  (113)   (114)
         (221)   (1113)
         (1112)  (1131)
         (1121)  (1221)
                 (2112)
                 (11112)
                 (11121)
                 (11211)
For example, the composition (2,1,1,2) has run-lengths (1,2,1), which are not weakly increasing, so (2,1,1,2) is counted under a(6).

Andrew Howroyd, Table of n, a(n) for n = 0..1000

The version for the compositions themselves (not run-lengths) is A056823.
The version for unsorted prime signature is A112769, with dual A071365.
The case without weakly decreasing run-lengths either is A332833.
The complement is counted by A332836.
Compositions that are not unimodal are A115981.
Compositions with equal run-lengths are A329738.
Compositions whose run-lengths are not unimodal are A332727.
Cf. A001523, A072704, A100883, A181819, A329744, A329766, A332641, A332669, A332726, A332745, A332746, A332834, A332835.

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],!LessEqual@@Length/@Split[#]&]],{n,0,10}]

a(n) = 2^(n - 1) - A332836(n).

Terms a(21) and beyond from Andrew Howroyd, Dec 30 2020

A353696 Numbers k such that the k-th composition in standard order (A066099) is empty, a singleton, or has run-lengths that are a consecutive subsequence that is already counted.

Original entry on oeis.org

0, 1, 2, 4, 8, 10, 16, 32, 43, 58, 64, 128, 256, 292, 349, 442, 512, 586, 676, 697, 826, 1024, 1210, 1338, 1393, 1394, 1396, 1594, 2048, 2186, 2234, 2618, 2696, 2785, 2786, 2792, 3130, 4096, 4282, 4410, 4666, 5178, 5569, 5570, 5572, 5576, 5584, 6202, 8192

Offset: 1

Gus Wiseman, May 22 2022

nonn

First differs from the non-consecutive version A353431 in lacking 22318, corresponding to the binary word 101011100101110 and standard composition (2,2,1,1,3,2,1,1,2), whose run-lengths (2,2,1,1,2,1) are a subsequence but not a consecutive 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 terms together with their corresponding compositions begin:
    0: ()
    1: (1)
    2: (2)
    4: (3)
    8: (4)
   10: (2,2)
   16: (5)
   32: (6)
   43: (2,2,1,1)
   58: (1,1,2,2)
   64: (7)
  128: (8)
  256: (9)
  292: (3,3,3)
  349: (2,2,1,1,2,1)
  442: (1,2,1,1,2,2)
  512: (10)
  586: (3,3,2,2)
  676: (2,2,3,3)
  697: (2,2,1,1,3,1)
  826: (1,3,1,1,2,2)

Non-recursive non-consecutive for partitions: A325755, counted by A325702.
Non-consecutive: A353431, counted by A353391.
Non-consecutive for partitions: A353393, counted by A353426.
Non-recursive non-consecutive: A353402, counted by A353390.
Counted by: A353430.
Non-recursive: A353432, counted by A353392.
A005811 counts runs in binary expansion.
A011782 counts compositions.
A066099 lists compositions in standard order, run-lengths A333769.
Statistics of standard compositions:
- Length is A000120, sum A070939.
- Runs are counted by A124767, distinct A351014.
- Subsequences are counted by A334299, contiguous A124770/A124771.
- Runs-resistance is A333628.
Classes of standard compositions:
- Partitions are A114994, strict A333255, multisets A225620, sets A333256.
- Runs are A272919, counted by A000005.
- Golomb rulers are A333222, counted by A169942.
- Anti-runs are A333489, counted by A003242.
Cf. A032020, A114640, A181819, A228351, A329739, A318928, A325705, A329738, A333224, A353427, A353403.

stc[n_]:=Differences[Prepend[Join@@ Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
yoyQ[y_]:=Length[y]<=1||MemberQ[Join@@Table[Take[y,{i,j}],{i,Length[y]},{j,i,Length[y]}],Length/@Split[y]]&&yoyQ[Length/@Split[y]];
Select[Range[0,1000],yoyQ[stc[#]]&]

cp's OEIS Frontend

A329866 Numbers whose binary expansion has its runs-resistance equal to its cuts-resistance minus 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A329868 Sorted positions of first appearances in A329867 (difference between the runs-resistance and the cuts-resistance of binary expansion) of each element in the image.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A333192 Number of compositions of n with strictly increasing run-lengths.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A353429 Number of integer compositions of n with all prime parts and all prime run-lengths.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A382774 Number of ways to permute the prime indices of n! so that the run-lengths are all different.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A383111 Number of integer partitions of n having more than one permutation with all distinct run-lengths.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Extensions

A329749 Number of complete compositions of n whose run-lengths cover an initial interval of positive integers.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs