A071163 -id:A071163 - 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)).

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))))))

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))).

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)).

A209643 A014486-indices for rooted plane trees where non-leaf branching can occur only at the leftmost branch of any level, but nowhere else.

Original entry on oeis.org

0, 1, 2, 3, 4, 6, 7, 8, 9, 14, 16, 17, 19, 20, 21, 22, 23, 37, 42, 44, 45, 51, 53, 54, 56, 57, 58, 60, 61, 62, 63, 64, 65, 107, 121, 126, 128, 129, 149, 154, 156, 157, 163, 165, 166, 168, 169, 170, 177, 179, 180, 182, 183, 184, 186, 187, 188, 189, 191, 192, 193, 194, 195, 196, 197, 329, 371, 385, 390, 392, 393, 461, 475, 480, 482

Offset: 0

Antti Karttunen, Mar 24 2012

nonn

5 is not member of this sequence, as it encodes in A014486 a general tree:
..|
\/
which has a nonempty branch which is not the leftmost child of its parent vertex.

Antti Karttunen, Table of n, a(n) for n = 0..32767
A. Karttunen, Corresponding trees illustrated on 1, 2, 3, 4, 6, 7, 8, 9, 14, 16, 17th, etc. row in this illustration.

Cf. A209644, A071163.

a(n) = A080300(A209641(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

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

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

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

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A209643 A014486-indices for rooted plane trees where non-leaf branching can occur only at the leftmost branch of any level, but nowhere else.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula