login
Zero followed by the terms of A023705 arranged to give the unique path to the n-th node of a complete, rooted and ordered ternary tree.
0

%I #27 Nov 21 2014 09:08:58

%S 0,1,2,3,5,9,13,6,10,14,7,11,15,21,37,53,25,41,57,29,45,61,22,38,54,

%T 26,42,58,30,46,62,23,39,55,27,43,59,31,47,63,85,149,213,101,165,229,

%U 117,181,245,89,153,217,105,169,233,121,185,249,93,157,221,109,173,237,125,189,253

%N Zero followed by the terms of A023705 arranged to give the unique path to the n-th node of a complete, rooted and ordered ternary tree.

%C There is no path to the root node so first node path is 0. All other paths are represented by the terms of A023705 that are base 4 numbers containing no zeros. Starting at the lowest order digit base 4, if this is 1 then the path from the root node is to the left, if it is 2 straight on and if it is 3 to the right. Each successive digit order defines the next path to be taken until the highest digit order is reached and the specified node found.

%H Adrian Rusu, <a href="http://cs.brown.edu/~rt/gdhandbook/chapters/trees.pdf">Tree Drawing Algorithms</a>, Rowan University.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/CompleteTernaryTree.html">Complete Ternary Tree</a>.

%e a(33)=39, so the path to the 33rd node is given by 39 and when represented as the base 4 number gives 213. Hence the path to the 33rd node from the root node is Right, Left, Straight.

%t tree=3; nest[{m2_, p2_}] := If[(mod=Mod[m2, tree])>1, (ind=mod-1; {(m2+tree-mod)/tree, ind+p2*(tree+1)}), (ind=tree+mod-1; {(m2-mod)/tree, ind+p2*(tree+1)})]; Table[NestWhile[nest, {n, 0}, #[[1]]!=1 &][[2]], {n, 1, 100}]

%Y Cf. A023705.

%K nonn

%O 1,3

%A _Frank M Jackson_, Nov 13 2014