login
This site is supported by donations to The OEIS Foundation.

 

Logo

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A106486 Number of edges in combinatorial game trees. 23
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,4

COMMENTS

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 kind 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 o r reversible options. Here a(n) gives the total number of edges in the tree f(n).

REFERENCES

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

LINKS

Table of n, a(n) for n=0..100.

EXAMPLE

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.

PROG

(MIT Scheme:) (define (A106486 n) (cond ((zero? n) 0) (else (fold-left (lambda (x y) (+ x y 1)) 0 (map A106486 (map shr (on-bit-indices n))))))) (define (shr n) (if (odd? n) (/ (- n 1) 2) (/ n 2))) (define (on-bit-indices n) (let loop ((n n) (i 0) (c (list))) (cond ((zero? n) (reverse! c)) ((odd? n) (loop (/ (- n 1) 2) (1+ i) (cons i c))) (else (loop (/ n 2) (1+ i) c)))))

CROSSREFS

Number of leaves: A106487, negating automorphism: A106485.

Sequence in context: A260651 A116370 A261018 * A195743 A106494 A015135

Adjacent sequences:  A106483 A106484 A106485 * A106487 A106488 A106489

KEYWORD

nonn

AUTHOR

Antti Karttunen, May 21 2005

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 16 15:31 EST 2019. Contains 319195 sequences. (Running on oeis4.)