This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.
%I A106486 #14 Nov 04 2024 09:15:32 %S A106486 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, %T A106486 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, %U A106486 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 %N A106486 Number of edges in combinatorial game trees. %C A106486 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). %D A106486 E. R. Berlekamp, J. H. Conway and R. K. Guy, Winning Ways, Second Edition, Vol. 1, A K Peters, 2001, p. 40. %e A106486 3 = 2^0 + 2^1 = 2^(2*0) + 2^((2*0)+1) encodes the CGT tree \/ which has two edges, thus a(3)=2. %e A106486 64 = 2^6 = 2^(2*3), i.e., it encodes the CGT tree %e A106486 \/ %e A106486 \ %e A106486 which has three edges, so a(64)=3. %o A106486 (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))))) %Y A106486 Number of leaves: A106487, negating automorphism: A106485. %K A106486 nonn %O A106486 0,4 %A A106486 _Antti Karttunen_, May 21 2005