A071162 -id:A071162 - cp's OEIS frontend

A209636 Matula-numbers computed for rooted trees encoded by A071162/A071163.

1, 2, 4, 3, 8, 6, 7, 5, 16, 12, 14, 10, 19, 13, 17, 11, 32, 24, 28, 20, 38, 26, 34, 22, 53, 37, 43, 29, 67, 41, 59, 31, 64, 48, 56, 40, 76, 52, 68, 44, 106, 74, 86, 58, 134, 82, 118, 62, 131, 89, 107, 71, 163, 101, 139, 79, 241, 157, 191, 109, 331, 179, 277

Offset: 0

Antti Karttunen, Mar 11 2012

Sequence is injective: Any number occurs at most once, as each plane tree encoded by A071162/A071163 is mapped to a unique non-oriented rooted tree. See also A209637, A209638.

Sequence A209638 gives the same terms sorted into ascending order.

Indranil Ghosh (terms 0..1000) & Antti Karttunen, Table of n, a(n) for n = 0..8191
Index entries for sequences related to binary expansion of n
Index entries for sequences related to Matula-Goebel numbers

Cf. A000040, A054429, A071162, A071163, A127301, A209637, A278541.

A209636(n) = { my(n=2*n, m=1); while(n >= 2, if(!(n%2),m*=2,m = prime(m)); n\=2); m; } \\ Antti Karttunen, May 25 2017

from sympy import prime
def a(n):
    n = 2*n
    m = 1
    if n<2: return 1
    while n>1:
        if n%2==0:
            n//=2
            m*=2
        else:
            n=(n - 1)//2
            m=prime(m)
    return m
print([a(n) for n in range(101)]) # Indranil Ghosh, May 25 2017, translated from Antti Karttunen's SCHEME code

(define (A209636 n) (let loop ((n (* 2 n)) (m 1)) (cond ((< n 2) m) ((even? n) (loop (/ n 2) (* m 2))) (else (loop (/ (- n 1) 2) (A000040 m))))))

a(n) = A127301(A071163(n)) = A209637(A054429(n)).

A209637 Matula-numbers computed for rooted trees encoded by A071162 when interpreted in once-halved bit-tuple format.

Original entry on oeis.org

1, 2, 3, 4, 5, 7, 6, 8, 11, 17, 13, 19, 10, 14, 12, 16, 31, 59, 41, 67, 29, 43, 37, 53, 22, 34, 26, 38, 20, 28, 24, 32, 127, 277, 179, 331, 109, 191, 157, 241, 79, 139, 101, 163, 71, 107, 89, 131, 62, 118, 82, 134, 58, 86, 74, 106, 44, 68, 52, 76, 40, 56, 48

Offset: 0

Antti Karttunen, Mar 11 2012

Sequence A209638 gives the same terms sorted into ascending order.

Mueller, Szymanski, Knop and Trinajstic, A Comparison between the Matula Numbers and Bit-tuple Notation for Rooted Trees J. Chem. Inf. Comput. Sci. 1995, 35, pp. 211--213.

from sympy import prime
from mpmath import log
def a054429(n): return 3*(2**int(log(n, 2))) - (n + 1)
def a209636(n):
    n = 2*n
    m = 1
    if n<2: return 1
    while n>1:
        if n%2==0:
            n/=2
            m*=2
        else:
            n=(n - 1)/2
            m=prime(m)
    return m
def a(n): return 1 if n==0 else a209636(a054429(n)) # Indranil Ghosh, May 26 2017

a(n) = A209636(A054429(n)) = A127301(A057505(A071163(n))) = A127301(A057163(A071163(n))).

A209642 A014486-codes for rooted plane trees where non-leaf branching can occur only at the leftmost branch of any level, but nowhere else. Reflected from the corresponding rightward branching codes in A071162, thus not in ascending order.

Original entry on oeis.org

0, 2, 10, 12, 42, 50, 52, 56, 170, 202, 210, 226, 212, 228, 232, 240, 682, 810, 842, 906, 850, 914, 930, 962, 852, 916, 932, 964, 936, 968, 976, 992, 2730, 3242, 3370, 3626, 3402, 3658, 3722, 3850, 3410, 3666, 3730, 3858, 3746, 3874, 3906, 3970, 3412, 3668, 3732, 3860, 3748, 3876, 3908, 3972, 3752, 3880, 3912, 3976, 3920, 3984, 4000, 4032

Offset: 0

Antti Karttunen, Mar 11 2012

Like with A071162, a(n) can be computed directly from the binary expansion of n. (See the Scheme function given). However, the function is not monotone. A209641 gives the same terms in ascending order.

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

a(n) = A209641(A209861(n)).

def a(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
print([a(n) for n in range(101)]) # Indranil Ghosh, May 25 2017, translated from Antti Karttunen's SCHEME code

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

a(n) = A056539(A071162(n)) = A036044(A071162(n)). (See also the given Scheme-function).

A209859 Rewrite the binary expansion of n from the most significant end, 1 -> 1, 0+1 (one or more zeros followed by one) -> 0, drop the trailing zeros of the original n.

Original entry on oeis.org

0, 1, 1, 3, 1, 2, 3, 7, 1, 2, 2, 5, 3, 6, 7, 15, 1, 2, 2, 5, 2, 4, 5, 11, 3, 6, 6, 13, 7, 14, 15, 31, 1, 2, 2, 5, 2, 4, 5, 11, 2, 4, 4, 9, 5, 10, 11, 23, 3, 6, 6, 13, 6, 12, 13, 27, 7, 14, 14, 29, 15, 30, 31, 63, 1, 2, 2, 5, 2, 4, 5, 11, 2, 4, 4, 9, 5, 10, 11, 23, 2, 4, 4, 9, 4, 8, 9, 19, 5, 10, 10, 21, 11, 22, 23, 47, 3, 6, 6, 13, 6, 12, 13, 27, 6, 12, 12, 25, 13

Offset: 0

Antti Karttunen, Mar 24 2012

This is the number k such that the k-th composition in standard order is the reversed sequence of lengths of the maximal anti-runs of the binary indices of n. Here, the binary indices of n are row n of A048793, and the k-th composition in standard order is row k of A066099. For example, the binary indices of 100 are {3,6,7}, with maximal anti-runs ((3,6),(7)), with reversed lengths (1,2), which is the 6th composition in standard order, so a(100) = 6. - Gus Wiseman, Jul 27 2025

			102 in binary is 1100110, we rewrite it from the left so that first two 1's stay same ("11"), then "001" is rewritten to "0", the last 1 to "1", and we ignore the last 0, thus getting 1101, which is binary expansion of 13, thus a(102) = 13.

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

This is an "inverse" of A071162, i.e. a(A071162(n)) = n for all n. Bisection: A209639. Used to construct permutation A209862.
Removing duplicates appears to give A358654.
Sorted positions of firsts appearances appear to be A247648+1.
A245563 lists run-lengths of binary indices (ranks A246029), reverse A245562.
A384175 counts subsets with all distinct lengths of maximal runs, complement A384176.
Cf. A000120, A023758, A029931, A044813, A048793, A052499, A069010, A348366, A384878, A384879, A384893.
Cf. A384877, A385816, A385887, A385889.

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}] (* Gus Wiseman, Jul 25 2025 *)

import re
def a(n): return int(re.sub("0+1", "0", bin(n)[2:].rstrip("0")), 2) if n else 0
print([a(n) for n in range(109)])  # Michael S. Branicky, Jul 25 2025

(define (A209859 n) (let loop ((n n) (s 0) (i (A053644 n))) (cond ((zero? n) s) ((> i n) (if (> (/ i 2) n) (loop n s (/ i 2)) (loop (- n (/ i 2)) (* 2 s) (/ i 4)))) (else (loop (- n i) (+ (* 2 s) 1) (/ i 2))))))

a(n) = a(A000265(n)).

A071163 A014486-indices 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, 1, 2, 3, 4, 5, 7, 8, 9, 10, 12, 13, 17, 18, 21, 22, 23, 24, 26, 27, 31, 32, 35, 36, 45, 46, 49, 50, 58, 59, 63, 64, 65, 66, 68, 69, 73, 74, 77, 78, 87, 88, 91, 92, 100, 101, 105, 106, 129, 130, 133, 134, 142, 143, 147, 148, 170, 171, 175, 176, 189, 190, 195, 196, 197

Offset: 0

Antti Karttunen, May 14 2002

nonn

This subset of integers is closed by the actions of A069770, A057163, A069767, A069768, A122353, A122354, A122301, A122302, etc. (meaning, e.g., that A069767(a(n)) is a member from this sequence for all n), that is, by any Catalan bijection which is an image of some element of the automorphism group of infinite binary tree (the latter in a sense given by Grigorchuk, et al., being isomorphic to an infinitely iterated wreath product of cyclic groups of two elements). See the comments about the isomorphism "psi" given at A153141.

a(n) could be probably computed directly from the binary expansion of n by using a (somewhat) similar ranking function as given in A209640, but utilizing A009766 instead of A007318.

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

a(n) = A080300(A071162(n)).

A071160 Łukasiewicz words that are also valid asynchronic siteswap juggling patterns.

Original entry on oeis.org

0, 1, 20, 11, 300, 201, 120, 111, 4000, 3001, 2020, 2011, 1300, 1201, 1120, 1111, 50000, 40001, 30020, 30011, 20300, 20201, 20120, 20111, 14000, 13001, 12020, 12011, 11300, 11201, 11120, 11111, 600000, 500001, 400020, 400011, 300300

Offset: 0

Antti Karttunen, May 14 2002

Note: this finite decimal representation works only up to the 511th term, as the 512th such word is already (10,0,0,0,0,0,0,0,0,0). The sequence A071161 shows the initial portion of this sequence sorted.

Peter J. Beek and Arthur Lewbel, The Science of Juggling, Scientific American, Nov, 1995, Vol. 273, Number 5, pp. 92-97.
Joe Buhler and R. L. Graham, Juggling Drops and Descents, Amer. Math. Monthly, 101, (no. 6) 1994, 507 - 519.
Juggling Information Service, Site Swap FAQs
A. Karttunen, Gatomorphisms and other excursions amidst the plane trees and parenthesizations (Includes the complete Scheme program for computing this sequence)
R. P. Stanley, Hipparchus, Plutarch, Schröder and Hough, Am. Math. Monthly, Vol. 104, No. 4, p. 344, 1997.
OEIS Wiki, Łukasiewicz words
Index entries for sequences related to Łukasiewicz

Subset of A071153.

Cf. A060495, A060498, A065177, A071162, A071163.

Construction: starting from the most significant (the leftmost) bit, replace each 1-bit in the binary expansion of n with the distance to the next 1-bit to the right, allowing a cyclic wrap-over from the least-significant 1-bit to the most significant 1-bit. I.e. from 22 = 10110 in binary we get 20120, the 22nd term of this sequence.

a(n) = A071161(A054429(n)).

cp's OEIS Frontend

A209636 Matula-numbers computed for rooted trees encoded by A071162/A071163.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Python

Scheme

Formula

A209637 Matula-numbers computed for rooted trees encoded by A071162 when interpreted in once-halved bit-tuple format.

Views

Author

Keywords

Comments

References

Programs

Python

Formula

A209642 A014486-codes for rooted plane trees where non-leaf branching can occur only at the leftmost branch of any level, but nowhere else. Reflected from the corresponding rightward branching codes in A071162, thus not in ascending order.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Python

Scheme

Formula

A209859 Rewrite the binary expansion of n from the most significant end, 1 -> 1, 0+1 (one or more zeros followed by one) -> 0, drop the trailing zeros of the original n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Scheme

Formula

A071163 A014486-indices 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

Formula

A071160 Łukasiewicz words that are also valid asynchronic siteswap juggling patterns.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula