A106487 -id:A106487 - cp's OEIS frontend

A106486 Number of edges in combinatorial game trees.

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

Offset: 0

Antti Karttunen, May 21 2005

nonn

Consider the following rooted trees useful in the combinatorial game theory: each tree has zero or more subtrees at its left side and zero or more subtrees at its right side. The orientation of the subtrees among the other branches of the same side is not distinguished and all the subtrees of the same side are distinct from each other. These kinds of trees map bijectively to nonnegative integers by the following map f: f(empty tree) = 0 and f(tree with left subtrees Tl1, ..., Tlj and right subtrees Tr1, ..., Trk) = 2^(2*f(Tl1)) + ... + 2^(2*f(Tlj)) + 2^((2*f(Tr1))+1) + ... + 2^((2*f(Trk))+1). The ten game trees given on page 40 of "Winning Ways" thus translate to values Game 0 -> 0, Game 1 -> 1, Game -1 -> 2, Game 2 -> 4, Game 1/2 -> 9, Game 1/4 -> 524289, Game * -> 3, Game 1* -> 12, Game *2 -> 195, Game ^ (up) -> 129. However, this correspondence is not bijective with the computed equivalence classes of games, as many integers map to game trees with dominated or reversible options. Here a(n) gives the total number of edges in the tree f(n).

			3 = 2^0 + 2^1 = 2^(2*0) + 2^((2*0)+1) encodes the CGT tree \/ which has two edges, thus a(3)=2.
64 = 2^6 = 2^(2*3), i.e., it encodes the CGT tree
  \/
   \
which has three edges, so a(64)=3.

E. R. Berlekamp, J. H. Conway and R. K. Guy, Winning Ways, Second Edition, Vol. 1, A K Peters, 2001, p. 40.

Number of leaves: A106487, negating automorphism: A106485.

A106485 CGT-tree negating involution of nonnegative integers.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, May 21 2005

nonn

This involution negates game trees used in the combinatorial game theory, when they are encoded in the way explained in A106486.

Cycles are confined into ranges [a(n),a(n+1)[, where a(0)=0 and a(n+1)=2^(2*a(n)), i.e. the ranges are [0,0], [1,3], [4,255], [256,(2^512)-1], ...

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

A057300 is a "shallow" version which just swaps the left and right options of the game tree, but does not reflect the subtrees themselves. Cf. A106486-A106487.

(define (A106485 n) (let loop ((n n) (i 0) (s 0)) (cond ((zero? n) s) ((odd? n) (loop (/ (- n 1) 2) (1+ i) (+ s (if (even? i) (expt 2 (+ 1 (* 2 (A106485 (/ i 2))))) (expt 2 (* 2 (A106485 (/ (- i 1) 2)))))))) (else (loop (/ n 2) (1+ i) s)))))

cp's OEIS Frontend

A106486 Number of edges in combinatorial game trees.

Views

Author

Keywords

Comments

Examples

References

Crossrefs

A106485 CGT-tree negating involution of nonnegative integers.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Scheme