A101211 -id:A101211 - cp's OEIS frontend

A294859 Triangle whose n-th row is the concatenated sequence of all Lyndon compositions of n in lexicographic order.

1, 2, 1, 2, 3, 1, 1, 2, 1, 3, 4, 1, 1, 1, 2, 1, 1, 3, 1, 2, 2, 1, 4, 2, 3, 5, 1, 1, 1, 1, 2, 1, 1, 1, 3, 1, 1, 2, 2, 1, 1, 4, 1, 2, 3, 1, 3, 2, 1, 5, 2, 4, 6, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 3, 1, 1, 1, 2, 2, 1, 1, 1, 4, 1, 1, 2, 1, 2, 1, 1, 2, 3, 1, 1, 3, 2, 1

Offset: 1

Gus Wiseman, Dec 18 2017

			Triangle of Lyndon compositions begins:
(1),
(2),
(12),(3),
(112),(13),(4),
(1112),(113),(122),(14),(23),(5),
(11112),(1113),(1122),(114),(123),(132),(15),(24),(6),
(111112),(11113),(11122),(1114),(11212),(1123),(1132),(115),(1213),(1222),(124),(133),(142),(16),(223),(25),(34),(7).

Cf. A000740, A001037, A001045, A008965, A059966, A060223, A066099, A101211, A102659, A124734, A185700, A228369, A281013, A296302, A296373, A296656.

LyndonQ[q_]:=Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And]&&Array[RotateRight[q,#]&,Length[q],1,UnsameQ];
Table[Sort[Select[Join@@Permutations/@IntegerPartitions[n],LyndonQ],OrderedQ[PadRight[{#1,#2}]]&],{n,7}]

Row n is a concatenation of A059966(n) Lyndon words with total length A000740(n).

A298644 The indices of the Carlitz compositions (i.e., compositions without adjacent equal parts).

Original entry on oeis.org

1, 3, 4, 6, 7, 8, 9, 14, 15, 16, 17, 24, 27, 28, 30, 31, 32, 33, 35, 36, 39, 48, 49, 54, 55, 57, 59, 60, 62, 63, 64, 65, 67, 68, 70, 72, 73, 78, 79, 96, 97, 99, 110, 111, 112, 118, 119, 120, 121, 123, 124, 126, 127, 128, 129, 131, 132, 134, 135, 136, 137, 143, 144, 145, 156, 158

Offset: 1

Emeric Deutsch, Jan 24 2018

nonn

We define the index of a composition to be the positive integer whose binary form has run-lengths (i.e., runs of 1's, runs of 0's, etc., from left to right) equal to the parts of the composition. Example: the composition [1,1,3,1] has index 46 since the binary form of 46 is 101110.

The command c(n) from the Maple program yields the composition having index n.

			135 is in the sequence since its binary form is 10000111 and the composition [1,4,3] has no adjacent equal parts.
139 is not in the sequence since its binary form is 10001011 and the composition [1,3,1,1,2] has two adjacent equal parts.

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

Cf. A003242, A101211.

Runs := proc (L) local j, r, i, k: j := 1: r[j] := L[1]: for i from 2 to nops(L) do if L[i] = L[i-1] then r[j] := r[j], L[i] else j := j+1: r[j] := L[i] end if end do: [seq([r[k]], k = 1 .. j)] end proc: RunLengths := proc (L) map(nops, Runs(L)) end proc: c := proc (n) ListTools:-Reverse(convert(n, base, 2)): RunLengths(%) end proc: pd := proc (n) options operator, arrow: product(c(n)[j]-c(n)[j+1], j = 1 .. nops(c(n))-1) end proc: A := {}; for n to 200 do if pd(n) <> 0 then A := `union`(A, {n}) else  end if end do: A; # most of the Maple program is due to W. Edwin Clark

With[{nn = 18}, TakeWhile[#, # <= Floor[2^(2 + nn/Log2[nn])] &] &@ Union@ Apply[Join, #] &@ Table[Map[FromDigits[#, 2] &@ Flatten@ MapIndexed[ConstantArray[Boole@ OddQ@ #2, #1] &, #] &, Select[Map[Flatten[Map[# /. w_List :> If[First@ w == 1, Length@ w + 1, ConstantArray[1, Length@ w]] &, Split@ #] /. {a__, b_List, c__} :> {a, Most@ b, c}] &@ PadLeft[#, n - 1] &, IntegerDigits[Range[0, 2^n - 1], 2]], FreeQ[Differences@ #, 0] &]], {n, 2, nn}]] (* Michael De Vlieger, Jan 24 2018 *)

A372516 Number of ones minus number of zeros in the binary expansion of the n-th prime number.

Original entry on oeis.org

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

Offset: 1

Gus Wiseman, May 13 2024

sign

Absolute value is A177718.

			The binary expansion of 83 is (1,0,1,0,0,1,1), and 83 is the 23rd prime, so a(23) = 4 - 3 = 1.

The sum instead of difference is A035100, firsts A372684 (primes A104080).
The negative version is A037861(A000040(n)).
Restriction of A145037 to the primes.
The unsigned version is A177718.
- Positions of zeros are A177796, indices of the primes A066196.
- Positions of positive terms are indices of the primes A095070.
- Positions of negative terms are indices of the primes A095071.
- Positions of negative ones are A372539, indices of the primes A095072.
- Positions of ones are A372538, indices of the primes A095073.
- Positions of nonnegative terms are indices of the primes A095074.
- Positions of nonpositive terms are indices of the primes A095075.
A000120 counts ones in binary expansion (binary weight), zeros A080791.
A030190 gives binary expansion, reversed A030308.
A035103 counts zeros in binary expansion of primes, firsts A372474.
A048793 lists binary indices, reverse A272020, sum A029931.
A070939 gives length of binary expansion.
A101211 lists run-lengths in binary expansion, row-lengths A069010.
A372471 lists the binary indices of each prime.
Cf. A000043, A003714, A005940, A059305, A061712, A066195, A071814, A211997, A372429, A372517, A372686.

Table[DigitCount[Prime[n],2,1]-DigitCount[Prime[n],2,0],{n,100}]
DigitCount[#,2,1]-DigitCount[#,2,0]&/@Prime[Range[100]] (* Harvey P. Dale, May 09 2025 *)

a(n) = A000120(A000040(n)) - A080791(A000040(n)).
a(n) = A014499(n) - A035103(n).
a(n) = A145037(A000040(n))

A227737 n occurs as many times as there are runs in binary representation of n.

Original entry on oeis.org

1, 2, 2, 3, 4, 4, 5, 5, 5, 6, 6, 7, 8, 8, 9, 9, 9, 10, 10, 10, 10, 11, 11, 11, 12, 12, 13, 13, 13, 14, 14, 15, 16, 16, 17, 17, 17, 18, 18, 18, 18, 19, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21, 21, 22, 22, 22, 22, 23, 23, 23, 24, 24, 25, 25, 25, 26, 26, 26, 26

Offset: 1

Antti Karttunen, Jul 25 2013

a(n) = the least integer k such that A173318(k) >= n, which implies that each n occurs A005811(n) times.

Although as such quite uninteresting, this sequence is useful for computing irregular tables like A101211, A227736, A227738 and A227739.

			1 has one run in its binary representation "1", thus 1 occurs once.
2 has two runs in its binary representation "10", thus 2 occurs twice.
3 has one run in its binary representation "11", thus 3 occurs only once.
4 has two runs in its binary representation "100", thus 4 occurs twice.
5 has three runs in its binary representation "101", thus 5 occurs three times.
The sequence thus begins as 1, 2,2, 3, 4,4, 5,5,5, ...

Antti Karttunen, Table of n, a(n) for n = 1..5120

Cf. A227740, A227741, A005811, A173318.

Table[ConstantArray[n, Length@ Split@ IntegerDigits[n, 2]], {n, 26}] // Flatten (* Michael De Vlieger, May 09 2017 *)
Table[PadRight[{},Length[Split[IntegerDigits[n,2]]],n],{n,40}]//Flatten (* Harvey P. Dale, Jul 23 2021 *)

A227738 Irregular table read by rows: each row n (n>=1) lists the positions where the runs of bits change between 0's and 1's in the binary expansion of n, when scanning it from the least significant to the most significant end.

Original entry on oeis.org

1, 1, 2, 2, 2, 3, 1, 2, 3, 1, 3, 3, 3, 4, 1, 3, 4, 1, 2, 3, 4, 2, 3, 4, 2, 4, 1, 2, 4, 1, 4, 4, 4, 5, 1, 4, 5, 1, 2, 4, 5, 2, 4, 5, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 3, 4, 5, 3, 4, 5, 3, 5, 1, 3, 5, 1, 2, 3, 5, 2, 3, 5, 2, 5, 1, 2, 5, 1, 5, 5, 5, 6, 1, 5, 6, 1, 2, 5, 6

Offset: 1

Antti Karttunen, Jul 25 2013

Row n has A005811(n) terms.
As a sequence, seems to have a particular fractal structure, probably allowing additional formulas.
Row n lists the positions of 1-bits in the binary expansion of the Gray code for n, A003188(n), when 1 is the rightmost position. A003188(17) = 25 = 11001_2 gives row 17: 1,4,5. - Alois P. Heinz, Feb 01 2023

			Table begins as:
  Row  n in    Terms on
   n   binary  that row
   1      1    1;
   2     10    1,2;
   3     11    2;
   4    100    2,3;
   5    101    1,2,3;
   6    110    1,3;
   7    111    3;
   8   1000    3,4;
   9   1001    1,3,4;
  10   1010    1,2,3,4;
  11   1011    2,3,4;
  12   1100    2,4;
  13   1101    1,2,4;
  14   1110    1,4;
  15   1111    4;
  16  10000    4,5;
etc.
The terms also give the partial sums of runlengths, when the binary expansion of n is scanned from the least significant to the most significant end.

Antti Karttunen, The rows 1..1023 of the table, flattened
Wikipedia, Gray code

Each row n (n>=1) contains the initial A005811(n) nonzero terms from the beginning of row n of A227188. A227192(n) gives the sum of terms on row n. A136480 gives the first column.
Cf. also A227188, A227736, A227739.
A318926 is a compressed version. If the order is reversed we get A101211 and A318927.
Cf. A003188, A360287.

T:= n-> (l-> seq(`if`(l[i]=1, i, [][]), i=1..nops(l)))(
                 Bits[Split](Bits[Xor](n, iquo(n, 2)))):
seq(T(n), n=1..50);  # Alois P. Heinz, Feb 01 2023

Table[Rest@FoldList[Plus,0,Length/@Split[Reverse[IntegerDigits[n,2]]]],{n,34}]//Flatten (* Wouter Meeussen, Aug 31 2013 *)

a(n) = A227188(A227737(n),A227740(n)).

Alternatively, if A227740(n) is 0, then a(n) = A227736(n), otherwise a(n) = a(n-1) + A227736(n). [Each row gives cumulative sums of the runlengths of binary representation of n]

A296772 Triangle read by rows in which row n lists the compositions of n ordered first by decreasing length and then reverse-lexicographically.

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 2, 3, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 2, 3, 1, 2, 2, 1, 3, 4, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 3, 1, 1, 2, 2, 1, 2, 1, 2, 1, 3, 1, 1, 2, 2, 1, 1, 3, 4, 1, 3, 2, 2, 3, 1, 4, 5, 1, 1, 1, 1, 1, 1, 2

Offset: 1

Gus Wiseman, Dec 20 2017

The ordering of compositions in each row is consistent with the reverse-Mathematica ordering of expressions (cf. A124734).

Length of k-th composition is A124748(k-1)+1. - Andrey Zabolotskiy, Dec 20 2017

			Triangle of compositions begins:
(1),
(11),(2),
(111),(21),(12),(3),
(1111),(211),(121),(112),(31),(22),(13),(4),
(11111),(2111),(1211),(1121),(1112),(311),(221),(212),(131),(122),(113),(41),(32),(23),(14),(5).

Cf. A066099, A101211, A108730, A124734, A124748, A228369, A281013, A294859, A296302, A296656, A296773, A296774.

Table[Reverse[Sort[Join@@Permutations/@IntegerPartitions[n]]],{n,6}]

A296773 Triangle read by rows in which row n lists the compositions of n ordered first by decreasing length and then lexicographically.

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 1, 1, 2, 2, 1, 3, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 1, 1, 3, 2, 2, 3, 1, 4, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 1, 1, 1, 1, 3, 1, 2, 2, 1, 3, 1, 2, 1, 2, 2, 2, 1, 3, 1, 1, 1, 4, 2, 3, 3, 2, 4, 1, 5, 1, 1, 1, 1, 1, 1, 1

Offset: 1

Gus Wiseman, Dec 20 2017

			Triangle of compositions begins:
(1),
(11),(2),
(111),(12),(21),(3),
(1111),(112),(121),(211),(13),(22),(31),(4),
(11111),(1112),(1121),(1211),(2111),(113),(122),(131),(212),(221),(311),(14),(23),(32),(41),(5).

Cf. A066099, A101211, A108730, A124734, A228369, A281013, A294859, A296302, A296656, A296772, A296774.

Table[Sort[Join@@Permutations/@IntegerPartitions[n],Or[Length[#1]>Length[#2],Length[#1]===Length[#2]&&OrderedQ[{#1,#2}]]&],{n,6}]

A037016 Numbers n with property that reading binary expansion from right to left (least significant to most significant), run lengths do not decrease.

Original entry on oeis.org

0, 1, 2, 3, 5, 6, 7, 10, 12, 13, 14, 15, 21, 25, 26, 28, 29, 30, 31, 42, 50, 51, 53, 56, 57, 58, 60, 61, 62, 63, 85, 101, 102, 106, 113, 114, 115, 117, 120, 121, 122, 124, 125, 126, 127, 170, 202, 204, 205, 213, 226, 227, 229, 230, 234, 240, 241, 242, 243, 245, 248

Offset: 1

N. J. A. Sloane

There are A000041(k) elements of this list consisting of k bits: a partition of k written in nonincreasing order corresponds to the binary expansion which when read left to right has run lengths as listed in the partition (reading left to right forces the initial run to be of 1s). - Jason Kimberley, Feb 08 2013
This sequence is a subsequence of A061854 (if we allow the initial 0 to be represented by the empty bit string). - Jason Kimberley, Feb 08 2013
The positive entries are those n for which row n of A101211 is weakly decreasing. Example: 6 is in the sequence because row 6 of A101211 is [2,1]; 8 is not in the sequence because row 8 of A101211 is [1,3]. - Emeric Deutsch, Jan 21 2018

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Index entries for sequences related to binary expansion of n

Cf. A037015 (subsequence), A037014, A037013.

import Data.List (unfoldr, group)
a037016 n = a037016_list !! (n-1)
a037016_list = 0 : filter
   (all (>= 0) . (\x -> zipWith (-) (tail $ rls x) $ rls x)) [1..] where
       rls = map length . group . unfoldr
             (\x -> if x == 0 then Nothing else Just $ swap $ divMod x 2)
-- Reinhard Zumkeller, Mar 10 2012

Select[ Range[0, 250], OrderedQ[ Reverse[ Length /@ Split[ IntegerDigits[#, 2] ] ] ]&] (* Jean-François Alcover, Apr 05 2013 *)

More terms from Patrick De Geest, Feb 15 1999

Offset fixed by Reinhard Zumkeller, Mar 10 2012

A227186 Array A(n,k) read by antidiagonals: the length of the (k+1)-th run (k>=0) of binary digits of n, first run starting from the least significant bit of n.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Jul 06 2013

A(n,k) is set to zero if there are less than k+1 runs.

The irregular table A101211 gives the nonzero terms of each row in reverse order. The terms on row n sum to A029837(n+1). The product of nonzero terms on row n>0 is A167489(n). Number of nonzero terms on each row: A005811.

			The top-left corner of the array:
0, 0, 0, 0, 0, ... (0, in binary 0, has no runs (by convention), thus at first we have all-0 sequence)
1, 0, 0, 0, 0, ... (1, in binary 1, has one run of length 1)
1, 1, 0, 0, 0, ... (2, in binary 10, has two runs of length 1 both)
2, 0, 0, 0, 0, ... (3, in binary 11, has one run of length 2)
2, 1, 0, 0, 0, ... (4, in binary 100, the rightmost run of length 2 given first, then the second run of length 1)
1, 1, 1, 0, 0, ... (5, in binary 101, has three runs of one bit each)
1, 2, 0, 0, 0, ...
3, 0, 0, 0, 0, ...
3, 1, 0, 0, 0, ...
1, 2, 1, 0, 0, ...
1, 1, 1, 1, 0, ...
2, 1, 1, 0, 0, ...
2, 2, 0, 0, 0, ...
1, 1, 2, 0, 0, ...
1, 3, 0, 0, 0, ...
4, 0, 0, 0, 0, ...

Antti Karttunen, The first 141 antidiagonals of the table, flattened

Used to compute A227183. Cf. also A163575, A227188, A227189.

A227186 := proc(n,k)
    local bdgs,ru,i,b,a;
    bdgs := convert(n,base,2) ;
    if nops(bdgs) = 0 then
        return 0 ;
    end if;
    ru := 0 ;
    i := 1 ;
    b := op(i,bdgs) ;
    a := 1 ;
    for i from 2 to nops(bdgs) do
        if op(i,bdgs) <> op(i-1,bdgs) then
            if ru = k then
                return a;
            end if;
            a := 1 ;
            ru := ru+1 ;
        else
            a := a+1 ;
        end if;
    end do:
    if ru =k then
        a ;
    else
        0 ;
    end if;
end proc: # R. J. Mathar, Jul 23 2013

A227186(n,k)=while(k>=0,for(c=1,n,bittest(n,0)==bittest(n\=2,0)&next;k&break;return(c));n||return;k--) \\ To let A(0,0)=1 add "!n||!" in front of while(...). TO DO: add default value k=-1 and implement "flattened" sequence, such that A227186(n) yields a(n). M. Hasler, Jul 21 2013

(define (A227186 n) (A227186bi (A002262 n) (A025581 n)))
(define (A227186bi n k) (cond ((< (A005811 n) (+ 1 k)) 0) ((zero? k) (A136480 n)) (else (A227186bi (A163575 n) (- k 1)))))

A(n,0) = A136480(n), n>0.

A227741 Simple self-inverse permutation of natural numbers: List each block of A005811(n) numbers from A173318(n-1)+1 to A173318(n) in reverse order.

Original entry on oeis.org

1, 3, 2, 4, 6, 5, 9, 8, 7, 11, 10, 12, 14, 13, 17, 16, 15, 21, 20, 19, 18, 24, 23, 22, 26, 25, 29, 28, 27, 31, 30, 32, 34, 33, 37, 36, 35, 41, 40, 39, 38, 44, 43, 42, 48, 47, 46, 45, 53, 52, 51, 50, 49, 57, 56, 55, 54, 60, 59, 58, 62, 61, 65, 64, 63, 69, 68, 67, 66

Offset: 1

Antti Karttunen, Jul 25 2013

nonn

This permutation maps between such irregular tables as A101211 and A227736 which are otherwise identical, except for the order in which the lengths of runs have been listed. In other words, A227736(n) = A101211(a(n)) and vice versa, A101211(n) = A227736(a(n)).

Antti Karttunen, Table of n, a(n) for n = 1..1001
Index entries for sequences that are permutations of the natural numbers

Cf. A227742 (gives the fixed points).

Cf. also A227737, A227740, A005811, A173318.

(define (A227741 n) (- (A173318 (A227737 n)) (A227740 n)))

a(n) = A173318(A227737(n)) - A227740(n).

cp's OEIS Frontend

A294859 Triangle whose n-th row is the concatenated sequence of all Lyndon compositions of n in lexicographic order.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Formula

A298644 The indices of the Carlitz compositions (i.e., compositions without adjacent equal parts).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A372516 Number of ones minus number of zeros in the binary expansion of the n-th prime number.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A227737 n occurs as many times as there are runs in binary representation of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A227738 Irregular table read by rows: each row n (n>=1) lists the positions where the runs of bits change between 0's and 1's in the binary expansion of n, when scanning it from the least significant to the most significant end.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A296772 Triangle read by rows in which row n lists the compositions of n ordered first by decreasing length and then reverse-lexicographically.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A296773 Triangle read by rows in which row n lists the compositions of n ordered first by decreasing length and then lexicographically.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

A037016 Numbers n with property that reading binary expansion from right to left (least significant to most significant), run lengths do not decrease.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Mathematica