A044813 -id:A044813 - cp's OEIS frontend

A005811 Number of runs in binary expansion of n (n>0); number of 1's in Gray code for n.

0, 1, 2, 1, 2, 3, 2, 1, 2, 3, 4, 3, 2, 3, 2, 1, 2, 3, 4, 3, 4, 5, 4, 3, 2, 3, 4, 3, 2, 3, 2, 1, 2, 3, 4, 3, 4, 5, 4, 3, 4, 5, 6, 5, 4, 5, 4, 3, 2, 3, 4, 3, 4, 5, 4, 3, 2, 3, 4, 3, 2, 3, 2, 1, 2, 3, 4, 3, 4, 5, 4, 3, 4, 5, 6, 5, 4, 5, 4, 3, 4, 5, 6, 5, 6, 7, 6, 5, 4, 5, 6, 5, 4, 5

Offset: 0

N. J. A. Sloane, Jeffrey Shallit, Simon Plouffe

Starting with a(1) = 0 mirror all initial 2^k segments and increase by one.
a(n) gives the net rotation (measured in right angles) after taking n steps along a dragon curve. - Christopher Hendrie (hendrie(AT)acm.org), Sep 11 2002
This sequence generates A082410: (0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, ...) and A014577; identical to the latter except starting 1, 1, 0, ...; by writing a "1" if a(n+1) > a(n); if not, write "0". E.g., A014577(2) = 0, since a(3) < a(2), or 1 < 2. - Gary W. Adamson, Sep 20 2003
Starting with 1 = partial sums of A034947: (1, 1, -1, 1, 1, -1, -1, 1, 1, 1, ...). - Gary W. Adamson, Jul 23 2008
The composer Per Nørgård's name is also written in the OEIS as Per Noergaard.
Can be used as a binomial transform operator: Let a(n) = the n-th term in any S(n); then extract 2^k strings, adding the terms. This results in the binomial transform of S(n). Say S(n) = 1, 3, 5, ...; then we obtain the strings: (1), (3, 1), (3, 5, 3, 1), (3, 5, 7, 5, 3, 5, 3, 1), ...; = the binomial transform of (1, 3, 5, ...) = (1, 4, 12, 32, 80, ...). Example: the 8-bit string has a sum of 32 with a distribution of (1, 3, 3, 1) or one 1, three 3's, three 5's, and one 7; as expected. - Gary W. Adamson, Jun 21 2012
Considers all positive odd numbers as nodes of a graph. Two nodes are connected if and only if the sum of the two corresponding odd numbers is a power of 2. Then a(n) is the distance between 2n + 1 and 1. - Jianing Song, Apr 20 2019

			Considered as a triangle with 2^k terms per row, the first few rows are:
  1
  2, 1
  2, 3, 2, 1
  2, 3, 4, 3, 2, 3, 2, 1
  ...
The n-th row becomes right half of next row; left half is mirrored terms of n-th row increased by one. - _Gary W. Adamson_, Jun 20 2012

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 0..10000
Joerg Arndt, Matters Computational (The Fxtbook).
J.-P. Allouche, G.-N. Han and J. Shallit, On some conjectures of P. Barry, arXiv:2006.08909 [math.NT], 2020.
J.-P. Allouche and J. Shallit, The Ring of k-regular Sequences, II.
J.-P. Allouche and J. Shallit, The ring of k-regular sequences, II, Theoret. Computer Sci., 307 (2003), 3-29.
Danielle Cox and Karyn McLellan, A problem on generation sets containing Fibonacci numbers, Fib. Quart., 55 (No. 2, 2017), 105-113.
Chandler Davis and Donald E. Knuth, Number Representations and Dragon Curves -- I and II, Journal of Recreational Mathematics, volume 3, number 2, April 1970, pages 66-81, and number 3, July 1970, pages 133-149. Reprinted with addendum in Donald E. Knuth, Selected Papers on Fun and Games, 2010, pages 571-614. Equation 3.2 g(n) = a(n-1).
Chandler Davis and Donald E. Knuth, Number Representations and Dragon Curves, Journal of Recreational Mathematics, volume 3, number 2, April 1970, pages 66-81, and number 3, July 1970, pages 133-149. [Cached copy, with permission]
P. Flajolet et al., Mellin Transforms And Asymptotics: Digital Sums, Theoret. Computer Sci. 23 (1994), 291-314.
P. Flajolet and Lyle Ramshaw, A note on Gray code and odd-even merge, SIAM J. Comput. 9 (1980), 142-158.
Sara Kropf and Stephan Wagner, q-Quasiadditive functions, arXiv:1605.03654 [math.CO], 2016.
Sara Kropf and S. Wagner, On q-Quasiadditive and q-Quasimultiplicative Functions, arXiv preprint arXiv:1608.03700 [math.CO], 2016.
Shuo Li, Palindromic length sequence of the ruler sequence and of the period-doubling sequence, arXiv:2007.08317 [math.CO], 2020.
Helmut Prodinger and Friedrich J. Urbanek, Infinite 0-1-Sequences Without Long Adjacent Identical Blocks, Discrete Mathematics, volume 28, issue 3, 1979, pages 277-289. Also first author's copy. Their "variation" v(k) at definition 3.4 is a(k).
Jeffrey Shallit, The mathematics of Per Noergaard's rhythmic infinity system, Fib. Q., 43 (2005), 262-268.
Ralf Stephan, Some divide-and-conquer sequences with (relatively) simple ordinary generating functions, 2004.
Ralf Stephan, Table of generating functions.
Index entries for "core" sequences.
Index entries for sequences related to binary expansion of n.

Cf. A037834 (-1), A088748 (+1), A246960 (mod 4), A034947 (first differences), A000975 (indices of record highs), A173318 (partial sums).
Cf. A056539, A014707, A014577, A082410, A030308, A090079, A044813, A165413, A226227, A226228, A226229.
Partial sums of A112347. Recursion depth of A035327.
Cf. A000120, A003188.

import Data.List (group)
a005811 0 = 0
a005811 n = length $ group $ a030308_row n
a005811_list = 0 : f [1] where
   f (x:xs) = x : f (xs ++ [x + x `mod` 2, x + 1 - x `mod` 2])
-- Reinhard Zumkeller, Feb 16 2013, Mar 07 2011

A005811 := proc(n)
    local i, b, ans;
    if n = 0 then
        return 0 ;
    end if;
    ans := 1;
    b := convert(n, base, 2);
    for i from nops(b)-1 to 1 by -1 do
        if b[ i+1 ]<>b[ i ] then
            ans := ans+1
        fi
    od;
    return ans ;
end proc:
seq(A005811(i), i=1..50) ;
# second Maple program:
a:= n-> add(i, i=Bits[Split](Bits[Xor](n, iquo(n, 2)))):
seq(a(n), n=0..100);  # Alois P. Heinz, Feb 01 2023

Table[ Length[ Length/@Split[ IntegerDigits[ n, 2 ] ] ], {n, 1, 255} ]
a[n_] := DigitCount[BitXor[n, Floor[n/2]], 2, 1]; Array[a, 100, 0] (* Amiram Eldar, Jul 11 2024 *)

a(n)=sum(k=1,n,(-1)^((k/2^valuation(k,2)-1)/2))

a(n)=if(n<1,0,a(n\2)+(a(n\2)+n)%2) \\ Benoit Cloitre, Jan 20 2014

a(n) = hammingweight(bitxor(n, n>>1));  \\ Gheorghe Coserea, Sep 03 2015

def a(n): return bin(n^(n>>1))[2:].count("1") # Indranil Ghosh, Apr 29 2017

a(2^k + i) = a(2^k - i + 1) + 1 for k >= 0 and 0 < i <= 2^k. - Reinhard Zumkeller, Aug 14 2001
a(2n+1) = 2a(n) - a(2n) + 1, a(4n) = a(2n), a(4n+2) = 1 + a(2n+1).
a(j+1) = a(j) + (-1)^A014707(j). - Christopher Hendrie (hendrie(AT)acm.org), Sep 11 2002
G.f.: (1/(1-x)) * Sum_{k>=0} x^2^k/(1+x^2^(k+1)). - Ralf Stephan, May 02 2003
Delete the 0, make subsets of 2^n terms; and reverse the terms in each subset to generate A088696. - Gary W. Adamson, Oct 19 2003
a(0) = 0, a(2n) = a(n) + [n odd], a(2n+1) = a(n) + [n even]. - Ralf Stephan, Oct 20 2003
a(n) = Sum_{k=1..n} (-1)^((k/2^A007814(k)-1)/2) = Sum_{k=1..n} (-1)^A025480(k-1). - Ralf Stephan, Oct 29 2003
a(n) = A069010(n) + A033264(n). - Ralf Stephan, Oct 29 2003
a(0) = 0 then a(n) = a(floor(n/2)) + (a(floor(n/2)) + n) mod 2. - Benoit Cloitre, Jan 20 2014
a(n) = A037834(n) + 1.
a(n) = A000120(A003188(n)). - Amiram Eldar, Jul 11 2024

Additional description from Wouter Meeussen

A239455 Number of Look-and-Say partitions of n; see Comments.

Original entry on oeis.org

0, 1, 2, 2, 4, 5, 7, 10, 13, 16, 21, 28, 33, 45, 55, 65, 83, 105, 121, 155, 180, 217, 259, 318, 362, 445, 512, 614, 707, 850, 958, 1155, 1309, 1543, 1754, 2079, 2327, 2740, 3085, 3592, 4042, 4699, 5253, 6093, 6815, 7839, 8751, 10069, 11208, 12832, 14266, 16270

Offset: 0

Clark Kimberling and Peter J. C. Moses, Mar 19 2014

nonn

Suppose that p = x(1) >= x(2) >= ... >= x(k) is a partition of n. Let y(1) > y(2) > ... > y(h) be the distinct parts of p, and let m(i) be the multiplicity of y(i) for 1 <= i <= h. Then we can "look" at p as "m(1) y(1)'s and m(2) y(2)'s and ... m(h) y(h)'s". Reversing the m's and y's, we can then "say" the Look-and-Say partition of p, denoted by LS(p). The name "Look-and-Say" follows the example of Look-and-Say integer sequences (e.g., A005150). As p ranges through the partitions of n, LS(p) ranges through all the Look-and-Say partitions of n. The number of these is A239455(n).
The Look-and-Say array is distinct from the Wilf array, described at A098859; for example, the number of Look-and-Say partitions of 9 is A239455(9) = 16, whereas the number of Wilf partitions of 9 is A098859(9) = 15. The Look-and-Say partition of 9 which is not a Wilf partition of 9 is [2,2,2,1,1,1].
Conjecture: a partition is Look-and-Say iff it has a permutation with all distinct run-lengths. For example, the partition y = (2,2,2,1,1,1) has the permutation (2,2,1,1,1,2), with run-lengths (2,3,1), which are all distinct, so y is counted under a(9). - Gus Wiseman, Aug 11 2025
Also the number of integer partitions y of n such that there is a pairwise disjoint way to choose a strict integer partition of each multiplicity (or run-length) of y. - Gus Wiseman, Aug 11 2025

			The 11 partitions of 6 generate 7 Look-and-Say partitions as follows:
6 -> 111111
51 -> 111111
42 -> 111111
411 -> 21111
33 -> 222
321 -> 111111
3111 -> 3111
222 -> 33
2211 -> 222
21111 -> 411
111111 -> 6,
so that a(6) counts these 7 partitions: 111111, 21111, 222, 3111, 33, 411, 6.

These include all Wilf partitions, counted by A098859, ranked by A130091.
These partitions are listed by A239454 in graded reverse-lex order.
Non-Wilf partitions are counted by A336866, ranked by A130092.
A variant for runs is A351204, complement A351203.
The complement is counted by A351293, apparently ranked by A351295, conjugate A381433.
These partitions appear to be ranked by A351294, conjugate A381432.
The non-Wilf case is counted by A351592.
For normal multisets we appear to have A386580, complement A386581.
A000110 counts set partitions, ordered A000670.
A000569 = graphical partitions, complement A339617.
A003242 and A335452 count anti-runs, ranks A333489, patterns A005649.
A181819 = Heinz number of the prime signature of n (prime shadow).
A279790 counts disjoint families on strongly normal multisets.
A329738 = compositions with all equal run-lengths.
A386583 counts separable partitions, sums A325534, ranks A335433.
A386584 counts inseparable partitions, sums A325535, ranks A335448.
A386585 counts separable type partitions, sums A336106, ranks A335127.
A386586 counts inseparable type partitions, sums A386638 or A025065, ranks A335126.
Counting words with all distinct run-lengths:
- A032020 = binary expansions, for runs A351018, ranked by A044813.
- A329739 = compositions, for runs A351013, ranked by A351596.
- A351017 = binary words, for runs A351016.
- A351292 = patterns, for runs A351200.
Cf. A000041, A008284, A047966, A182857, A225485, A297770, A304660, A305563, A329746, A351201, A351202, A351291.

LS[part_List] := Reverse[Sort[Flatten[Map[Table[#[[2]], {#[[1]]}] &, Tally[part]]]]]; LS[n_Integer] := #[[Reverse[Ordering[PadRight[#]]]]] &[DeleteDuplicates[Map[LS, IntegerPartitions[n]]]]; TableForm[t = Map[LS[#] &, Range[10]]](*A239454,array*)
Flatten[t](*A239454,sequence*)
Map[Length[LS[#]] &, Range[25]](*A239455*)
(* Peter J. C. Moses, Mar 18 2014 *)
disjointFamilies[y_]:=Select[Tuples[IntegerPartitions/@Length/@Split[y]],UnsameQ@@Join@@#&];
Table[Length[Select[IntegerPartitions[n],Length[disjointFamilies[#]]>0&]],{n,0,10}] (* Gus Wiseman, Aug 11 2025 *)

A351294 Numbers whose multiset of prime factors has at least one permutation with all distinct run-lengths.

Original entry on oeis.org

1, 2, 3, 4, 5, 7, 8, 9, 11, 12, 13, 16, 17, 18, 19, 20, 23, 24, 25, 27, 28, 29, 31, 32, 37, 40, 41, 43, 44, 45, 47, 48, 49, 50, 52, 53, 54, 56, 59, 61, 63, 64, 67, 68, 71, 72, 73, 75, 76, 79, 80, 81, 83, 88, 89, 92, 96, 97, 98, 99, 101, 103, 104, 107, 108, 109

Offset: 1

Gus Wiseman, Feb 15 2022

nonn

First differs from A130091 (Wilf partitions) in having 216.
See A239455 for the definition of Look-and-Say partitions.
The Heinz number of a partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k). This gives a bijective correspondence between positive integers and integer partitions.

			The terms together with their prime indices begin:
      1: ()            20: (3,1,1)         47: (15)
      2: (1)           23: (9)             48: (2,1,1,1,1)
      3: (2)           24: (2,1,1,1)       49: (4,4)
      4: (1,1)         25: (3,3)           50: (3,3,1)
      5: (3)           27: (2,2,2)         52: (6,1,1)
      7: (4)           28: (4,1,1)         53: (16)
      8: (1,1,1)       29: (10)            54: (2,2,2,1)
      9: (2,2)         31: (11)            56: (4,1,1,1)
     11: (5)           32: (1,1,1,1,1)     59: (17)
     12: (2,1,1)       37: (12)            61: (18)
     13: (6)           40: (3,1,1,1)       63: (4,2,2)
     16: (1,1,1,1)     41: (13)            64: (1,1,1,1,1,1)
     17: (7)           43: (14)            67: (19)
     18: (2,2,1)       44: (5,1,1)         68: (7,1,1)
     19: (8)           45: (3,2,2)         71: (20)
For example, the prime indices of 216 are {1,1,1,2,2,2}, and there are four permutations with distinct run-lengths: (1,1,2,2,2,1), (1,2,2,2,1,1), (2,1,1,1,2,2), (2,2,1,1,1,2); so 216 is in the sequence. It is the Heinz number of the Look-and-Say partition of (3,3,2,1).

The Wilf case (distinct multiplicities) is A130091, counted by A098859.
The complement of the Wilf case is A130092, counted by A336866.
These partitions appear to be counted by A239455.
A variant for runs is A351201, counted by A351203 (complement A351204).
The complement is A351295, counted by A351293.
A032020 = number of binary expansions with distinct run-lengths.
A044813 = numbers whose binary expansion has all distinct run-lengths.
A056239 = sum of prime indices, row sums of A112798.
A165413 = number of run-lengths in binary expansion, for all runs A297770.
A181819 = Heinz number of prime signature (prime shadow).
A182850/A323014 = frequency depth, counted by A225485/A325280.
A320922 ranks graphical partitions, complement A339618, counted by A000569.
A329739 = compositions with all distinct run-lengths, for all runs A351013.
A333489 ranks anti-runs, complement A348612.
A351017 = binary words with all distinct run-lengths, for all runs A351016.
A351292 = patterns with all distinct run-lengths, for all runs A351200.
Cf. A000961, A001221, A001222, A047966, A175413, A182857, A304660, A320924, A328592, A329747, A351202, A351290, A351592.

Select[Range[100],Select[Permutations[Join@@ ConstantArray@@@FactorInteger[#]],UnsameQ@@Length/@Split[#]&]!={}&]

Name edited by Gus Wiseman, Aug 13 2025

A351293 Number of non-Look-and-Say partitions of n. Number of integer partitions of n such that there is no way to choose a disjoint strict integer partition of each multiplicity.

Original entry on oeis.org

0, 0, 0, 1, 1, 2, 4, 5, 9, 14, 21, 28, 44, 56, 80, 111, 148, 192, 264, 335, 447, 575, 743, 937, 1213, 1513, 1924, 2396, 3011, 3715, 4646, 5687, 7040, 8600, 10556, 12804, 15650, 18897, 22930, 27593, 33296, 39884, 47921, 57168, 68360, 81295, 96807, 114685

Offset: 0

Gus Wiseman, Feb 16 2022

nonn

First differs from A336866 (non-Wilf partitions) at a(9) = 14, A336866(9) = 15, the difference being the partition (2,2,2,1,1,1).

See A239455 for the definition of Look-and-Say partitions.

			The a(3) = 1 through a(9) = 14 partitions:
  (21)  (31)  (32)  (42)    (43)    (53)     (54)
              (41)  (51)    (52)    (62)     (63)
                    (321)   (61)    (71)     (72)
                    (2211)  (421)   (431)    (81)
                            (3211)  (521)    (432)
                                    (3221)   (531)
                                    (3311)   (621)
                                    (4211)   (3321)
                                    (32111)  (4221)
                                             (4311)
                                             (5211)
                                             (32211)
                                             (42111)
                                             (321111)

The complement is counted by A239455, ranked by A351294.
These are all non-Wilf partitions (counted by A336866, ranked by A130092).
A variant for runs is A351203, complement A351204, ranked by A351201.
These partitions appear to be ranked by A351295.
Non-Wilf partitions in the complement are counted by A351592.
A000569 = graphical partitions, complement A339617.
A032020 = number of binary expansions with all distinct run-lengths.
A044813 = numbers whose binary expansion has all distinct run-lengths.
A098859 = Wilf partitions (distinct multiplicities), ranked by A130091.
A181819 = Heinz number of the prime signature of n (prime shadow).
A329738 = compositions with all equal run-lengths.
A329739 = compositions with all distinct run-lengths, for all runs A351013.
A351017 = binary words with all distinct run-lengths, for all runs A351016.
A351292 = patterns with all distinct run-lengths, for all runs A351200.
Cf. A000041, A008284, A047966, A182857, A225485, A238130, A297770, A304660, A305563, A329740, A329746, A351202, A351291.

disjointFamilies[y_]:=Select[Tuples[IntegerPartitions/@Length/@Split[y]],UnsameQ@@Join@@#&];
Table[Length[Select[IntegerPartitions[n],Length[disjointFamilies[#]]==0&]],{n,0,15}] (* Gus Wiseman, Aug 13 2025 *)

a(n) = A000041(n) - A239455(n).

Edited by Gus Wiseman, Aug 12 2025

A351295 Numbers whose multiset of prime factors has no permutation with all distinct run-lengths.

Original entry on oeis.org

6, 10, 14, 15, 21, 22, 26, 30, 33, 34, 35, 36, 38, 39, 42, 46, 51, 55, 57, 58, 60, 62, 65, 66, 69, 70, 74, 77, 78, 82, 84, 85, 86, 87, 90, 91, 93, 94, 95, 100, 102, 105, 106, 110, 111, 114, 115, 118, 119, 120, 122, 123, 126, 129, 130, 132, 133, 134, 138, 140

Offset: 1

Gus Wiseman, Feb 16 2022

nonn

First differs from A130092 (non-Wilf partitions) in lacking 216.

The Heinz number of a partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k). This gives a bijective correspondence between positive integers and integer partitions.

			The terms together with their prime indices begin:
      6: (2,1)         46: (9,1)         84: (4,2,1,1)
     10: (3,1)         51: (7,2)         85: (7,3)
     14: (4,1)         55: (5,3)         86: (14,1)
     15: (3,2)         57: (8,2)         87: (10,2)
     21: (4,2)         58: (10,1)        90: (3,2,2,1)
     22: (5,1)         60: (3,2,1,1)     91: (6,4)
     26: (6,1)         62: (11,1)        93: (11,2)
     30: (3,2,1)       65: (6,3)         94: (15,1)
     33: (5,2)         66: (5,2,1)       95: (8,3)
     34: (7,1)         69: (9,2)        100: (3,3,1,1)
     35: (4,3)         70: (4,3,1)      102: (7,2,1)
     36: (2,2,1,1)     74: (12,1)       105: (4,3,2)
     38: (8,1)         77: (5,4)        106: (16,1)
     39: (6,2)         78: (6,2,1)      110: (5,3,1)
     42: (4,2,1)       82: (13,1)       111: (12,2)
For example, the prime indices of 150 are {1,2,3,3}, with permutations and run-lengths (right):
  (3,3,2,1) -> (2,1,1)
  (3,3,1,2) -> (2,1,1)
  (3,2,3,1) -> (1,1,1,1)
  (3,2,1,3) -> (1,1,1,1)
  (3,1,3,2) -> (1,1,1,1)
  (3,1,2,3) -> (1,1,1,1)
  (2,3,3,1) -> (1,2,1)
  (2,3,1,3) -> (1,1,1,1)
  (2,1,3,3) -> (1,1,2)
  (1,3,3,2) -> (1,2,1)
  (1,3,2,3) -> (1,1,1,1)
  (1,2,3,3) -> (1,1,2)
Since none have all distinct run-lengths, 150 is in the sequence.

Wilf partitions are counted by A098859, ranked by A130091.
Non-Wilf partitions are counted by A336866, ranked by A130092.
A variant for runs is A351201, counted by A351203 (complement A351204).
These partitions appear to be counted by A351293.
The complement is A351294, apparently counted by A239455.
A032020 = number of binary expansions with distinct run-lengths.
A044813 = numbers whose binary expansion has all distinct run-lengths.
A056239 = sum of prime indices, row sums of A112798.
A165413 = number of distinct run-lengths in binary expansion.
A181819 = Heinz number of prime signature (prime shadow).
A182850/A323014 = frequency depth, counted by A225485/A325280.
A297770 = number of distinct runs in binary expansion.
A320922 ranks graphical partitions, complement A339618, counted by A000569.
A329739 = compositions with all distinct run-lengths, for all runs A351013.
A329747 = runs-resistance, counted by A329746.
A333489 ranks anti-runs, complement A348612.
A351017 = binary words with all distinct run-lengths, for all runs A351016.
Cf. A000961, A001221, A001222, A175413, A182857, A304660, A320924, A328592, A351202, A351290.

Select[Range[100],Select[Permutations[Join@@ ConstantArray@@@FactorInteger[#]],UnsameQ@@Length/@Split[#]&]=={}&]

Name edited by Gus Wiseman, Aug 13 2025

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

Original entry on oeis.org

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

Offset: 0

Gus Wiseman, Feb 07 2022

nonn

The n-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 n, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions.

			The number 3310 has binary expansion 110011101110 and standard composition (1,3,1,1,2,1,1,2), with runs (1), (3), (1,1), (2), (1,1), (2), of which 4 are distinct, so a(3310) = 4.

Mathematics Stack Exchange, What is a sequence run? (answered 2011-12-01)

Counting not necessarily distinct runs gives A124767.
Using binary expansions instead of standard compositions gives A297770.
Positions of first appearances are A351015.
A005811 counts runs in binary expansion.
A011782 counts integer compositions.
A044813 lists numbers whose binary expansion has distinct run-lengths.
A085207 represents concatenation of standard compositions, reverse A085208.
A333489 ranks anti-runs, complement A348612.
A345167 ranks alternating compositions, counted by A025047.
A351204 counts partitions where every permutation has all distinct runs.
Counting words with all distinct runs:
- A351013 = compositions, for run-lengths A329739, ranked by A351290.
- A351016 = binary words, for run-lengths A351017.
- A351018 = binary expansions, for run-lengths A032020, ranked by A175413.
- A351200 = patterns, for run-lengths A351292.
- A351202 = permutations of prime factors.
Selected statistics of standard compositions:
- Length is A000120.
- Sum is A070939.
- Heinz number is A333219.
- Number of distinct parts is A334028.
Selected classes of standard compositions:
- Partitions are A114994, strict A333256.
- Multisets are A225620, strict A333255.
- Strict compositions are A233564.
- Constant compositions are A272919.
Cf. A098859, A106356, A116608, A238279, A242882, A318928, A325545, A328592, A329745, A350952, A351201.

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

A351013 Number of integer compositions of n with all distinct runs.

Original entry on oeis.org

1, 1, 2, 4, 7, 14, 26, 48, 88, 161, 294, 512, 970, 1634, 2954, 5156, 9119, 15618, 27354, 46674, 80130, 138078, 232286, 394966, 665552, 1123231, 1869714, 3146410, 5186556, 8620936, 14324366, 23529274, 38564554, 63246744, 103578914, 167860584, 274465845

Offset: 0

Gus Wiseman, Feb 09 2022

nonn

			The a(1) = 1 through a(5) = 14 compositions:
  (1)  (2)    (3)      (4)        (5)
       (1,1)  (1,2)    (1,3)      (1,4)
              (2,1)    (2,2)      (2,3)
              (1,1,1)  (3,1)      (3,2)
                       (1,1,2)    (4,1)
                       (2,1,1)    (1,1,3)
                       (1,1,1,1)  (1,2,2)
                                  (2,2,1)
                                  (3,1,1)
                                  (1,1,1,2)
                                  (1,1,2,1)
                                  (1,2,1,1)
                                  (2,1,1,1)
                                  (1,1,1,1,1)
For example, the composition c = (3,1,1,1,1,2,1,1,3,4,1,1) has runs (3), (1,1,1,1), (2), (1,1), (3), (4), (1,1), and since (3) and (1,1) both appear twice, c is not counted under a(20).

Andrew Howroyd, Table of n, a(n) for n = 0..1000
Mathematics Stack Exchange, What is a sequence run? (answered 2011-12-01)

The version for run-lengths instead of runs is A329739, normal A329740.
These compositions are ranked by A351290, complement A351291.
A000005 counts constant compositions, ranked by A272919.
A005811 counts runs in binary expansion.
A011782 counts integer compositions.
A059966 counts binary Lyndon compositions, necklaces A008965, aperiodic A000740.
A116608 counts compositions by number of distinct parts.
A238130 and A238279 count compositions by number of runs.
A242882 counts compositions with distinct multiplicities.
A297770 counts distinct runs in binary expansion.
A325545 counts compositions with distinct differences.
A329744 counts compositions by runs-resistance.
A351014 counts distinct runs in standard compositions.
Counting words with all distinct runs:
- A351016 = binary words, for run-lengths A351017.
- A351018 = binary expansions, for run-lengths A032020, ranked by A175413.
- A351200 = patterns, for run-lengths A351292.
- A351202 = permutations of prime factors.
Cf. A003242, A025047, A044813, A098504, A098859, A106356, A329738, A328592, A334028, A351015, A351201, A351204.

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

\\ here LahI is A111596 as row polynomials.
LahI(n,y) = {sum(k=1, n, y^k*(-1)^(n-k)*(n!/k!)*binomial(n-1, k-1))}
S(n) = {my(p=prod(k=1, n, 1 + y*x^k + O(x*x^n))); 1 + sum(i=1, (sqrtint(8*n+1)-1)\2, polcoef(p,i,y)*LahI(i,y))}
seq(n)={my(q=S(n)); [subst(serlaplace(p),y,1) | p<-Vec(prod(k=1, n, subst(q + O(x*x^(n\k)), x, x^k)))]} \\ Andrew Howroyd, Feb 12 2022

Terms a(26) and beyond from Andrew Howroyd, Feb 12 2022

A175413 Those positive integers n that when written in binary, the lengths of the runs of 1 are distinct and the lengths of the runs of 0's are distinct.

Original entry on oeis.org

1, 2, 3, 4, 6, 7, 8, 11, 12, 13, 14, 15, 16, 19, 23, 24, 25, 28, 29, 30, 31, 32, 35, 38, 39, 44, 47, 48, 49, 50, 52, 55, 56, 57, 59, 60, 61, 62, 63, 64, 67, 70, 71, 78, 79, 88, 92, 95, 96, 97, 98, 103, 104, 111, 112, 113, 114, 115, 116, 120, 121, 123, 124, 125

Offset: 1

Leroy Quet, May 07 2010

A044813 contains those positive integers that when written in binary, have all run-lengths (of both 0's and 1's) distinct.
A175414 contains those positive integers in A175413 that are not in A044813. (A175414 contains those positive integers that when written in binary, at least one run of 0's is the same length as one run of 1's, even though all run of 0 are of distinct length and all runs of 1's are of distinct length.)
Also numbers whose binary expansion has all distinct runs (not necessarily run-lengths). - Gus Wiseman, Feb 21 2022

Alois P. Heinz, Table of n, a(n) for n = 1..20000

Cf. A044813, A175414.
Runs in binary expansion are counted by A005811, distinct A297770.
The complement is A351205.
The version for standard compositions is A351290, complement A351291.
A000120 counts binary weight.
A242882 counts compositions with distinct multiplicities.
A318928 gives runs-resistance of binary expansion.
A325545 counts compositions with distinct differences.
A333489 ranks anti-runs, complement A348612, counted by A003242.
A334028 counts distinct parts in standard compositions.
A351014 counts distinct runs in standard compositions.
Counting words with all distinct runs:
- A351013 = compositions, for run-lengths A329739.
- A351016 = binary words, for run-lengths A351017.
- A351018 = binary expansions, for run-lengths A032020.
- A351200 = patterns, for run-lengths A351292.
- A351202 = permutations of prime factors.
Cf. A070939, A085207, A098859, A233564, A238130 or A238279, A283353, A328592, A350952, A351015, A351203.

q:= proc(n) uses ListTools; (l-> is(nops(l)=add(
      nops(i), i={Split(`=`, l, 1)}) +add(
      nops(i), i={Split(`=`, l, 0)})))(Bits[Split](n))
    end:
select(q, [$1..200])[];  # Alois P. Heinz, Mar 14 2022

f[n_] := And@@Unequal@@@Transpose[Partition[Length/@Split[IntegerDigits[n, 2]], 2, 2, {1,1}, 0]]; Select[Range[125], f] (* Ray Chandler, Oct 21 2011 *)
Select[Range[0,100],UnsameQ@@Split[IntegerDigits[#,2]]&] (* Gus Wiseman, Feb 21 2022 *)

from itertools import groupby, product
def ok(n):
    runs = [(k, len(list(g))) for k, g in groupby(bin(n)[2:])]
    return len(runs) == len(set(runs))
print([k for k in range(1, 125) if ok(k)]) # Michael S. Branicky, Feb 22 2022

Extended by Ray Chandler, Oct 21 2011

A353852 Numbers k such that the k-th composition in standard order (row k of A066099) has all distinct run-sums.

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 15, 16, 17, 18, 19, 20, 21, 23, 24, 26, 28, 30, 31, 32, 33, 34, 35, 36, 37, 38, 40, 41, 42, 43, 44, 47, 48, 50, 51, 52, 55, 56, 57, 58, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 79, 80, 81, 84, 85, 86, 87, 88

Offset: 0

Gus Wiseman, May 31 2022

nonn

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.

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 terms together with their binary expansions and corresponding compositions begin:
   0:        0  ()
   1:        1  (1)
   2:       10  (2)
   3:       11  (1,1)
   4:      100  (3)
   5:      101  (2,1)
   6:      110  (1,2)
   7:      111  (1,1,1)
   8:     1000  (4)
   9:     1001  (3,1)
  10:     1010  (2,2)
  12:     1100  (1,3)
  15:     1111  (1,1,1,1)
  16:    10000  (5)
  17:    10001  (4,1)
  18:    10010  (3,2)
  19:    10011  (3,1,1)
  20:    10100  (2,3)
  21:    10101  (2,2,1)
  23:    10111  (2,1,1,1)

The version for runs in binary expansion is A175413.
The version for parts instead of run-sums is A233564, counted A032020.
The version for run-lengths instead of run-sums is A351596, counted A329739.
The version for runs instead of run-sums is A351290, counted by A351013.
The version for partitions is A353838, counted A353837, complement A353839.
The equal instead of distinct version is A353848, counted by A353851.
These compositions are counted by A353850.
The weak version (rucksack compositions) is A354581, counted by A354580.
A003242 counts anti-run compositions, ranked by A333489.
A005811 counts runs in binary expansion.
A011782 counts compositions.
A242882 counts composition with distinct multiplicities, partitions A098859.
A304442 counts partitions with all equal run-sums.
A351014 counts distinct runs in standard compositions, firsts A351015.
A353853-A353859 pertain to composition run-sum trajectory.
A353864 counts rucksack partitions, perfect A353865.
A353929 counts distinct runs in binary expansion, firsts A353930.
Cf. A044813, A238279, A333755, A351016, A351017, A353832, A353847, A353849, A353860, A353863, A353932.

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

cp's OEIS Frontend

A357527 Reverse run lengths in binary expansions of terms of A044813: for n > 0, a(n) is the unique k such that A044813(k) = A056539(A044813(n)); a(0) = 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A005811 Number of runs in binary expansion of n (n>0); number of 1's in Gray code for n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

PARI

Python

Formula

Extensions

A239455 Number of Look-and-Say partitions of n; see Comments.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A351294 Numbers whose multiset of prime factors has at least one permutation with all distinct run-lengths.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions

A351293 Number of non-Look-and-Say partitions of n. Number of integer partitions of n such that there is no way to choose a disjoint strict integer partition of each multiplicity.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

Extensions

A351295 Numbers whose multiset of prime factors has no permutation with all distinct run-lengths.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs