A106485 CGT-tree negating involution of nonnegative integers.

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

Author

Antti Karttunen, May 21 2005

Keywords

• nonn

Comments

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], ...

Links

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

Crossrefs

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.

Programs

Scheme

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