A209859 -id:A209859 - cp's OEIS frontend

A209639 Bisection of A209859.

1, 3, 2, 7, 2, 5, 6, 15, 2, 5, 4, 11, 6, 13, 14, 31, 2, 5, 4, 11, 4, 9, 10, 23, 6, 13, 12, 27, 14, 29, 30, 63, 2, 5, 4, 11, 4, 9, 10, 23, 4, 9, 8, 19, 10, 21, 22, 47, 6, 13, 12, 27, 12, 25, 26, 55, 14, 29, 28, 59, 30, 61, 62, 127, 2, 5, 4, 11, 4, 9, 10, 23, 4, 9, 8, 19, 10, 21, 22, 47, 4, 9, 8, 19, 8, 17, 18, 39, 10, 21, 20, 43, 22, 45, 46, 95, 6, 13, 12

Offset: 0

Antti Karttunen, Mar 24 2012

Antti Karttunen, Table of n, a(n) for n = 0..65535

a(n) = A209859(A005408(n)).

A209862 Permutation of nonnegative integers which maps A209642 into ascending order (A209641).

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 11, 13, 14, 15, 16, 17, 18, 20, 24, 19, 21, 25, 22, 26, 28, 23, 27, 29, 30, 31, 32, 33, 34, 36, 40, 48, 35, 37, 41, 49, 38, 42, 50, 44, 52, 56, 39, 43, 51, 45, 53, 57, 46, 54, 58, 60, 47, 55, 59, 61, 62, 63, 64, 65, 66, 68, 72, 80, 96, 67, 69, 73, 81, 97, 70, 74, 82, 98, 76, 84, 100, 88, 104, 112, 71, 75, 83

Offset: 0

Antti Karttunen, Mar 24 2012

nonn

Conjecture: For all n, a(A054429(n)) = A054429(a(n)), i.e. A054429 acts as a homomorphism (automorphism) of the cyclic group generated by this permutation. This implies also a weaker conjecture given in A209860.
From Gus Wiseman, Aug 24 2021: (Start)
As a triangle with row lengths 2^n, T(n,k) for n > 0 appears (verified up to n = 2^15) to be the unique nonnegative integer whose binary indices are the k-th subset of {1..n} containing n. Here, a binary index of n (row n of A048793) is any position of a 1 in its reversed binary expansion, and sets are sorted first by length, then lexicographically. For example, the triangle begins:
   1
   2  3
   4  5  6  7
   8  9 10 12 11 13 14 15
  16 17 18 20 24 19 21 25 22 26 28 23 27 29 30 31
Mathematica: Table[Total[2^(Append[#,n]-1)]&/@Subsets[Range[n-1]],{n,5}]
Row lengths are A000079 (shifted right). Also Column k = 1.
Row sums are A010036.
Using reverse-lexicographic order gives A059893.
Using lexicographic order gives A059894.
Taking binary indices to prime indices gives A339195 (or A019565).
The ordering of sets is A344084.
A version using Heinz numbers is A344085.
(End)

			From _Gus Wiseman_, Aug 24 2021: (Start)
The terms, their binary expansions, and their binary indices begin:
   0:      ~ {}
   1:    1 ~ {1}
   2:   10 ~ {2}
   3:   11 ~ {1,2}
   4:  100 ~ {3}
   5:  101 ~ {1,3}
   6:  110 ~ {2,3}
   7:  111 ~ {1,2,3}
   8: 1000 ~ {4}
   9: 1001 ~ {1,4}
  10: 1010 ~ {2,4}
  12: 1100 ~ {3,4}
  11: 1011 ~ {1,2,4}
  13: 1101 ~ {1,3,4}
  14: 1110 ~ {2,3,4}
  15: 1111 ~ {1,2,3,4}
(End)

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

Inverse permutation: A209861. Cf. A209860, A209863, A209864, A209865, A209866, A209867, A209868.

Cf. A010036, A026793, A048793, A111059, A147655, A246688, A246867, A261144, A272020, A294648, A339360.

a(n) = A209859(A036044(A209641(n))) = A209859(A056539(A209641(n))).

A385816 The number k such that the k-th composition in standard order lists the maximal anti-run lengths of the binary indices of n. Standard composition number of row n of A384877.

Original entry on oeis.org

0, 1, 1, 3, 1, 2, 3, 7, 1, 2, 2, 6, 3, 5, 7, 15, 1, 2, 2, 6, 2, 4, 6, 14, 3, 5, 5, 13, 7, 11, 15, 31, 1, 2, 2, 6, 2, 4, 6, 14, 2, 4, 4, 12, 6, 10, 14, 30, 3, 5, 5, 13, 5, 9, 13, 29, 7, 11, 11, 27, 15, 23, 31, 63, 1, 2, 2, 6, 2, 4, 6, 14, 2, 4, 4, 12, 6, 10, 14

Offset: 0

Gus Wiseman, Jul 15 2025

nonn

A binary index of n is any position of a 1 in its reversed binary expansion. The binary indices of n are row n of A048793.
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.
If the k-th composition in standard order is y, then the standard composition number of y is defined to be k.

			The binary indices of 181 are {1,3,5,6,8}, with maximal anti-runs ((1,3,5),(6,8)), with lengths (3,2), which is the 18th composition in standard order, so a(181) = 18.

Gus Wiseman, Statistics, classes, and transformations of standard compositions

The reverse version is A209859.
Sorted positions of first appearances are A247648.
These are standard composition numbers of rows of A384877 (duplicates removed A385886).
For runs instead of anti-runs the reverse is A385887 (duplicates removed A232559).
For runs instead of anti-runs we have A385889 (duplicates removed A385818).
A245563 lists run lengths of binary indices (ranks A246029), reverse A245562.
Cf. A000120, A029931, A044813, A048793, A052499, A069010, A348366, A384175, A384878, A384879, A384893.

bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
stcinv[q_]:=Total[2^(Accumulate[Reverse[q]])]/2;
stcinv/@Table[Length/@Split[bpe[n],#2!=#1+1&],{n,0,100}]

A385889 The number k such that the k-th composition in standard order is the sequence of lengths of maximal runs of binary indices of n.

Original entry on oeis.org

0, 1, 1, 2, 1, 3, 2, 4, 1, 3, 3, 5, 2, 6, 4, 8, 1, 3, 3, 5, 3, 7, 5, 9, 2, 6, 6, 10, 4, 12, 8, 16, 1, 3, 3, 5, 3, 7, 5, 9, 3, 7, 7, 11, 5, 13, 9, 17, 2, 6, 6, 10, 6, 14, 10, 18, 4, 12, 12, 20, 8, 24, 16, 32, 1, 3, 3, 5, 3, 7, 5, 9, 3, 7, 7, 11, 5, 13, 9, 17, 3

Offset: 0

Gus Wiseman, Jul 16 2025

nonn

A binary index of n is any position of a 1 in its reversed binary expansion. The binary indices of n are row n of A048793.

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 binary indices of 27 are {1,2,4,5}, with maximal runs ((1,2),(4,5)), with lengths (2,2), which is the 10th composition in standard order, so a(27) = 10.
The binary indices of 100 are {3,6,7}, with maximal runs ((3),(6,7)), with lengths (1,2), which is the 6th composition in standard order, so a(100) = 6.

Gus Wiseman, Statistics, classes, and transformations of standard compositions

Sorted positions of firsts appearances appear to be A247648+1.
After removing duplicates we get A385818.
The reverse version is A385887.
A245563 lists run lengths of binary indices (ranks A246029), reverse A245562.
A384877 lists anti-run lengths of binary indices (ranks A385816), reverse A209859.
Cf. A000120, A023758, A029931, A044813, A048793, A069010, A348366, A384175, A384878, A385817.

bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
stcinv[q_]:=Total[2^(Accumulate[Reverse[q]])]/2;
Table[stcinv[Length/@Split[bpe[n],#2==#1+1&]],{n,0,100}]

A071162 Simple rewriting of binary expansion of n resulting A014486-codes for rooted binary trees with height equal to number of internal vertices. (Binary trees where at each internal vertex at least the other child is leaf).

Original entry on oeis.org

0, 2, 10, 12, 42, 44, 52, 56, 170, 172, 180, 184, 212, 216, 232, 240, 682, 684, 692, 696, 724, 728, 744, 752, 852, 856, 872, 880, 936, 944, 976, 992, 2730, 2732, 2740, 2744, 2772, 2776, 2792, 2800, 2900, 2904, 2920, 2928, 2984, 2992, 3024, 3040, 3412, 3416

Offset: 0

Antti Karttunen, May 14 2002

Essentially rewrites in binary expansion of n each 0 -> 01, 1X -> 1(rewrite X)0, where X is the maximal suffix after the 1-bit, which will be rewritten recursively (see the given Scheme-function). Because of this, the terms of the binary length 2n are counted by 2's powers, A000079.
In rooted plane (general) tree context, these are those totally balanced binary sequences (terms of A014486) where non-leaf subtrees can occur only as the rightmost branch (at any level of a general tree), but nowhere else. (Cf. A209642).
Also, these are exactly those rooted plane trees whose Łukasiewicz words happen to be valid asynchronous siteswap juggling patterns. (This was the original, albeit quite frivolous definition of this sequence for almost ten years 2002-2012. Cf. A071160.)

Antti Karttunen, Table of n, a(n) for n = 0..65535
OEIS Wiki, Łukasiewicz words
Index entries for sequences related to Łukasiewicz

a(n) = A014486(A071163(n)) = A036044(A209642(n)) = A056539(A209642(n)).
A209859 provides an "inverse" function, i.e. A209859(a(n)) = n for all n.
Cf. A209636, A209637, A209862.

def a036044(n): return int(''.join('1' if i == '0' else '0' for i in bin(n)[2:][::-1]), 2)
def a209642(n):
    s=0
    i=1
    while n!=0:
        if n%2==0:
            n//=2
            s=4*s + 1
        else:
            n=(n - 1)//2
            s=(s + i)*2
        i*=4
    return s
def a(n): return 0 if n==0 else a036044(a209642(n))
print([a(n) for n in range(101)]) # Indranil Ghosh, May 25 2017

(define (A071162 n) (let loop ((n n) (s 0) (i 1)) (cond ((zero? n) s) ((even? n) (loop (/ n 2) (+ s i) (* i 4))) (else (loop (/ (- n 1) 2) (* 2 (+ s i)) (* i 4))))))

A385818 The number k such that the k-th composition in standard order lists the maximal run lengths of each nonnegative integer's binary indices, with duplicates removed.

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 6, 8, 7, 9, 10, 12, 16, 11, 13, 17, 14, 18, 20, 24, 32, 15, 19, 21, 25, 33, 22, 26, 34, 28, 36, 40, 48, 64, 23, 27, 35, 29, 37, 41, 49, 65, 30, 38, 42, 50, 66, 44, 52, 68, 56, 72, 80, 96, 128, 31, 39, 43, 51, 67, 45, 53, 69, 57, 73, 81, 97

Offset: 0

Gus Wiseman, Jul 18 2025

nonn

A permutation of the nonnegative integers.
A binary index of n is any position of a 1 in its reversed binary expansion. The binary indices of n are row n of A048793.
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 binary indices of 53 are {1,3,5,6}, with maximal runs ((1),(3),(5,6)) with lengths (1,1,2), which is the 14th composition in standard order, so A385889(53) = 14, and after removing duplicate rows a(16) = 14.

For anti-runs instead of runs we appear to have A348366.
See also A385816 (standard compositions of rows of A384877), reverse A209859.
The compositions themselves are listed by A385817.
Before removing duplicates we had A385889.
A245563 lists run lengths of binary indices (ranks A246029), rev A245562, strict A328592.
A384175 counts subsets with all distinct lengths of maximal runs, complement A384176.
Cf. A000120, A029931, A048793, A052499, A069010, A200648, A200649, A200650, A384890, A385886, A385887.

bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
stcinv[q_]:=Total[2^(Accumulate[Reverse[q]])]/2;
stcinv/@DeleteDuplicates[Table[Length/@Split[bpe[n],#2==#1+1&],{n,0,100}]]

A385887 The number k such that the k-th composition in standard order is the reversed sequence of lengths of maximal runs of binary indices of n.

Original entry on oeis.org

0, 1, 1, 2, 1, 3, 2, 4, 1, 3, 3, 6, 2, 5, 4, 8, 1, 3, 3, 6, 3, 7, 6, 12, 2, 5, 5, 10, 4, 9, 8, 16, 1, 3, 3, 6, 3, 7, 6, 12, 3, 7, 7, 14, 6, 13, 12, 24, 2, 5, 5, 10, 5, 11, 10, 20, 4, 9, 9, 18, 8, 17, 16, 32, 1, 3, 3, 6, 3, 7, 6, 12, 3, 7, 7, 14, 6, 13, 12, 24

Offset: 0

Gus Wiseman, Jul 17 2025

nonn

A binary index of n is any position of a 1 in its reversed binary expansion. The binary indices of n are row n of A048793.

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 binary indices of 100 are {3,6,7}, with maximal runs ((3),(6,7)), with reversed lengths (2,1), which is the 5th composition in standard order, so a(100) = 5.

Gus Wiseman, Statistics, classes, and transformations of standard compositions

Removing duplicates appears to give A232559, see also A348366, A358654, A385818.
Sorted positions of firsts appearances appear to be A247648+1.
The non-reverse version is A385889.
A245563 lists run-lengths of binary indices (ranks A246029), reverse A245562.
A384877 lists anti-run lengths of binary indices (ranks A385816), reverse A209859.
Cf. A000120, A029931, A044813, A048793, A069010, A384175, A385817, A385886.

bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
stcinv[q_]:=Total[2^(Accumulate[Reverse[q]])]/2;
Table[stcinv[Reverse[Length/@Split[bpe[n],#2==#1+1&]]],{n,0,100}]

cp's OEIS Frontend

A209639 Bisection of A209859.

Views

Author

Keywords

Links

Formula

A209862 Permutation of nonnegative integers which maps A209642 into ascending order (A209641).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A385816 The number k such that the k-th composition in standard order lists the maximal anti-run lengths of the binary indices of n. Standard composition number of row n of A384877.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A385889 The number k such that the k-th composition in standard order is the sequence of lengths of maximal runs of binary indices of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A071162 Simple rewriting of binary expansion of n resulting A014486-codes for rooted binary trees with height equal to number of internal vertices. (Binary trees where at each internal vertex at least the other child is leaf).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Python

Scheme

A385818 The number k such that the k-th composition in standard order lists the maximal run lengths of each nonnegative integer's binary indices, with duplicates removed.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A385887 The number k such that the k-th composition in standard order is the reversed sequence of lengths of maximal runs of binary indices of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica