A036044 -id:A036044 - cp's OEIS frontend

A080070 Decimal encoding of parenthesizations produced by simple iteration starting from empty parentheses and where each successive parenthesization is obtained from the previous by reflecting it as a general tree/parenthesization, then adding an extra stem below the root and then reflecting the underlying binary tree.

0, 10, 1010, 101100, 10110010, 1011100100, 101100110100, 10111001001100, 1011100110100010, 101110011010011000, 10110011101001100010, 1011110010011011000100, 101100111011010001100100

Offset: 0

Antti Karttunen, Jan 27 2003

Corresponding Lisp/Scheme S-expressions are (), (()), (()()), (()(())), (()(())()), (()((())())), (()(())(()())), ...

Conjecture: only the terms in positions 0,1,2 and 4 are symmetric, i.e., A057164(A080068(n)) = A080068(n) (equivalently: A036044(A080069(n)) = A080069(n)) only when n is one of {0,1,2,4}. If this is true, then the formula given in A079438 is exact. I (AK) have checked this up to n=404631 with no other occurrence of a symmetric (general) tree.

			This demonstrates how to get the fourth term 10110010 from the 3rd term 101100. The corresponding binary and general trees plus parenthesizations are shown. The first operation reflects the general tree, the second adds a new stem under the root and the third reflects the underlying binary tree, which induces changes on the corresponding general tree:
..............................................
.....\/................\/\/..........\/\/.....
......\/......\/\/......\/............\/......
.....\/........\/........\/..........\/.......
......(A057164).(A057548)..(A057163)..........
........................o.....................
........................|.....................
........o.....o.........o...o.........o.......
........|.....|..........\./..........|.......
....o...o.....o...o.......o.........o.o.o.....
.....\./.......\./........|..........\|/......
......*.........*.........*...........*.......
..[()(())]..[(())()]..[((())())]..[()(())()]..
...101100....110010....11100100....10110010...

A. Karttunen, Illustration of initial terms
A. Karttunen, Python program for computing this sequence.
A. Karttunen, Terms a(1)-a(256) plotted as a Wolframesque triangle.
A. Karttunen, Terms a(1)-a(512) plotted as a Wolframesque triangle.

Compare to similar Wolframesque plots given in A122229, A122232, A122235, A122239, A122242, A122245. See also A079438, A080067, A080071, A057119.

a(n) = A007088(A080069(n)) = A063171(A080068(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))).

A080973 A014486-encoding of the "Moose trees".

Original entry on oeis.org

2, 52, 14952, 4007632, 268874213792, 68836555442592, 4561331969745081152, 300550070677246403229312, 1294530259719904904564091957759232, 331402554328705507772604330809117952

Offset: 0

Antti Karttunen, Mar 02 2003

nonn

Meeussen's observation about the orbits of a composition of two involutions F and R states that if the orbit size of the composition (acting on a particular element of the set) is odd, then it contains an element fixed by the other involution if and only if it contains also an element fixed by the other, on the (almost) opposite side of the cycle. Here those two involutions are A057163 and A057164, their composition is Donaghey's "Map M" A057505 and as the trees A080293/A080295 are symmetric as binary trees and the cycle sizes A080292 are odd, it follows that these are symmetric as general trees.

Antti Karttunen, Initial terms illustrated

Same sequence in binary: A080974. A036044(a(n)) = a(n) for all n. The number of edges (as general trees): A080978.

a(n) = A014486(A080975(n)) = A014486(A057505^((A080292(n)+1)/2) (A080293(n))) [where ^ stands for the repeated applications of permutation A057505.]

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

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

A126310 A014486-index for the Dyck path "derived" from the n-th Dyck path encoded by A014486(n).

Original entry on oeis.org

0, 0, 1, 0, 2, 1, 1, 1, 0, 4, 2, 2, 2, 1, 2, 1, 2, 3, 1, 1, 1, 1, 0, 9, 4, 4, 4, 2, 4, 2, 4, 5, 2, 2, 2, 2, 1, 4, 2, 2, 2, 1, 4, 2, 6, 7, 3, 2, 2, 3, 1, 2, 1, 2, 3, 1, 2, 3, 3, 1, 1, 1, 1, 1, 0, 23, 9, 9, 9, 4, 9, 4, 9, 10, 4, 4, 4, 4, 2, 9, 4, 4, 4, 2, 9, 4, 11, 12, 5, 4, 4, 5, 2, 4, 2, 4, 5, 2, 4, 5, 5

Offset: 0

Antti Karttunen, Jan 02 2007

nonn

According to Vaillé, the concept of "dérivation des ponts" is defined by Kreweras, in "Sur les éventails de segments" paper.

G. Kreweras, Sur les éventails de segments, Cahiers du Bureau Universitaire de Recherche Opérationelle, Cahier no. 15, Paris, 1970, pp. 3-41.
J. Vaillé, Une Bijection Explicative de Plusieurs Propriétés Remarquables des Ponts, European J. Combin. 18 (1997), no. 1, 117-124.

Cf. A125986, A126309, A125985.

a(n) = A125986(A126309(A125985(n))).

A253608 The binary representation of a(n) is the concatenation of n and the binary complement of n, A035327(n).

Original entry on oeis.org

2, 9, 12, 35, 42, 49, 56, 135, 150, 165, 180, 195, 210, 225, 240, 527, 558, 589, 620, 651, 682, 713, 744, 775, 806, 837, 868, 899, 930, 961, 992, 2079, 2142, 2205, 2268, 2331, 2394, 2457, 2520, 2583, 2646, 2709, 2772, 2835, 2898, 2961, 3024, 3087, 3150, 3213

Offset: 1

Alex Ratushnyak, Jan 05 2015

Michael De Vlieger, Table of n, a(n) for n = 1..10000

Cf. A035327, A036044, A070939.

a:= n-> (n+1)*(2^(ilog2(n)+1)-1):
seq(a(n), n=1..50);  # Alois P. Heinz, Jan 08 2015

Array[(# + 1) (2^(Floor@ Log2[#] + 1) - 1) &, 50] (* Michael De Vlieger, Oct 13 2018 *)

a(n) = (n+1)*(2^#binary(n)-1); \\ Michel Marcus, Jan 08 2015

for n in range(1,333):
  print(str((n+1)*(2 ** int.bit_length(int(n))-1)), end=',')

a(n) = (n+1) * (2^BL(n) - 1), where BL(n) is the binary length of n.

A284797 Write in base k, complement, reverse. Case k = 3.

Original entry on oeis.org

2, 1, 0, 7, 4, 1, 6, 3, 0, 25, 16, 7, 22, 13, 4, 19, 10, 1, 24, 15, 6, 21, 12, 3, 18, 9, 0, 79, 52, 25, 70, 43, 16, 61, 34, 7, 76, 49, 22, 67, 40, 13, 58, 31, 4, 73, 46, 19, 64, 37, 10, 55, 28, 1, 78, 51, 24, 69, 42, 15, 60, 33, 6, 75, 48, 21, 66, 39, 12, 57, 30

Offset: 0

Paolo P. Lava, Apr 03 2017

			a(9) = 25 because 9 in base 3 is 100, its complement in base 3 is 122 and the digit reverse is 221 that is 25 in base 10.

Harvey P. Dale, Table of n, a(n) for n = 0..1000

Cf. A036044, A267193, A284798.

P:=proc(q,h) local a,b,k,n; print(h-1); for n from 1 to q do a:=convert(n,base,h); b:=0;
for k from 1 to nops(a) do a[k]:=h-1-a[k]; b:=h*b+a[k]; od; print(b); od; end: P(10^2,3);

Table[FromDigits[Reverse[2-IntegerDigits[n,3]],3],{n,0,70}] (* Harvey P. Dale, Sep 08 2019 *)

from gmpy2 import digits
def A284797(n): return -int((s:=digits(n,3)[::-1]),3)-1+3**len(s) # Chai Wah Wu, Feb 04 2022

A284799 Write in base k, complement, reverse. Case k = 4.

Original entry on oeis.org

3, 2, 1, 0, 14, 10, 6, 2, 13, 9, 5, 1, 12, 8, 4, 0, 62, 46, 30, 14, 58, 42, 26, 10, 54, 38, 22, 6, 50, 34, 18, 2, 61, 45, 29, 13, 57, 41, 25, 9, 53, 37, 21, 5, 49, 33, 17, 1, 60, 44, 28, 12, 56, 40, 24, 8, 52, 36, 20, 4, 48, 32, 16, 0, 254, 190, 126, 62, 238, 174

Offset: 0

Paolo P. Lava, Apr 03 2017

			a(16) = 62 because 16 in base 4 is 100, its complement in base 4 is 233 and the digit reverse is 332 that is 64 in base 10.

Robert Israel, Table of n, a(n) for n = 0..10000

Cf. A036044, A267193, A284800.

P:=proc(q,h) local a,b,k,n; print(h-1); for n from 1 to q do a:=convert(n,base,h); b:=0;
for k from 1 to nops(a) do a[k]:=h-1-a[k]; b:=h*b+a[k]; od; print(b); od; end: P(10^2,4);

With[{k = 4}, Array[FromDigits[Reverse[k - IntegerDigits[#, k] - 1], k] &, 70, 0]] (* Michael De Vlieger, Feb 04 2022 *)

from gmpy2 import digits
def A284799(n): return -int((s:=digits(n,4)[::-1]),4)-1+4**len(s) # Chai Wah Wu, Feb 04 2022

a(a(n))=n unless n == 3 (mod 4). - Robert Israel, Apr 01 2020

A284807 Write in base k, complement, reverse. Case k = 8.

Original entry on oeis.org

7, 6, 5, 4, 3, 2, 1, 0, 62, 54, 46, 38, 30, 22, 14, 6, 61, 53, 45, 37, 29, 21, 13, 5, 60, 52, 44, 36, 28, 20, 12, 4, 59, 51, 43, 35, 27, 19, 11, 3, 58, 50, 42, 34, 26, 18, 10, 2, 57, 49, 41, 33, 25, 17, 9, 1, 56, 48, 40, 32, 24, 16, 8, 0, 510, 446, 382, 318, 254

Offset: 0

Paolo P. Lava, Apr 03 2017

			a(16) = 61 because 16 in base 8 is 20, its complement in base 8 is 57 and the digit reverse is 75 that is 61 in base 10.

Michael De Vlieger, Table of n, a(n) for n = 0..10000

Cf. A036044, A267193, A284808.

P:=proc(q,h) local a,b,k,n; print(h-1); for n from 1 to q do a:=convert(n,base,h); b:=0;
for k from 1 to nops(a) do a[k]:=h-1-a[k]; b:=h*b+a[k]; od; print(b); od; end: P(10^2,8);

With[{k = 8}, Array[FromDigits[Reverse[k - IntegerDigits[#, k] - 1], k] &, 69, 0]] (* Michael De Vlieger, Feb 04 2022 *)

def A284807(n): return -int((s:=oct(n)[-1:1:-1]),8)-1+8**len(s) # Chai Wah Wu, Feb 04 2022

Offset corrected by Chai Wah Wu, Feb 04 2022

cp's OEIS Frontend

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A080973 A014486-encoding of the "Moose trees".

Views

Author

Keywords

Comments

Links

Crossrefs

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

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

A126310 A014486-index for the Dyck path "derived" from the n-th Dyck path encoded by A014486(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A253608 The binary representation of a(n) is the concatenation of n and the binary complement of n, A035327(n).

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

A284797 Write in base k, complement, reverse. Case k = 3.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

A284799 Write in base k, complement, reverse. Case k = 4.

Views