A106487 Number of leaves in combinatorial game trees.

1, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5

Offset

0,4

Comments

See the comment at A106486.

After n=0 differs from A000120 for the first time at n=64, where A000120(64)=1, while a(64)=2.

Links

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

Example

3 = 2^0 + 2^1 = 2^(2*0) + 2^((2*0)+1) encodes the CGT tree \/ which has two terminal nodes, thus a(3)=2.
64 = 2^6 = 2^(2*3), i.e. it encodes the CGT tree
\/
.\
which also has two terminal (non-root) nodes, so a(64)=2.

Prog

(Scheme:) (define (A106487 n) (cond ((zero? n) 1) (else (apply + (map A106487 (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

Cf. A000120, A106486.

Sequence in context: A105164 A000120 A105062 * A105102 A105105 A178677

Adjacent sequences: A106484 A106485 A106486 * A106488 A106489 A106490

Keyword

nonn

Author

Antti Karttunen, May 21 2005

Status

approved