Knuth's Power Tree and Related Sequences

[Hugo Pfoertner]

"Paul D. Hanna" wrote:
> 
> Seqfans,
>       Would someone like to compute more terms of Knuth's Power Tree?
> It apparently is NOT in the OEIS, but seems that it should be.
> The terms below I simply copied from the book (see reference below),
> so I hope that I do not have a typo.
> 
> I am mostly interested in knowing these 2 related sequences:
> * number of nodes in rows:   1,1,2,3,5,9,15,26,...
> * row sums:   1,2,7,19,54,164,476,1417,...
> but am having difficulty computing the above.
> 
> Can anyone help generate these 3 new sequences?
> 
> Thanks,
>        Paul
> =================================================

Paul, SeqFans,

Donald E. Knuth describes an efficient method to construct the power
tree in "Answers to exercises"  for Section 4.6.3 page 692, exercise 5
is given on page 481 TAOCP Vol. 2.

I wrote a small Fortran program implementing Knuth's algorithm:

http://www.randomwalk.de/sequences/pwrtree.txt
producing the following results in a few CPU seconds:

level  leftmost  number      row sums
       node in   of nodes
       row       in row
  2       2       1              2
  3       3       2              7
  4       5       3             19
  5       7       5             54
  6      14       9            164
  7      19      15            476
  8      38      26           1417
  9      57      43           4087
 10      71      78          12589
 11     142     134          37818
 12     284     238         116828
 13     568     415         358277
 14     571     731        1106870
 15    1142    1299        3460676
 16    2284    2299       10813998
 17    4568    4126       34339769
 18    9136    7374      109194390
 19   18272   13257      350181146
 20   36544   23847     1126919513
 21   36545   42864     3634208553
 22   73089   77366    11774823887
 23  146178  140071    38335906599
 24  292356  254241   125461951555
 25  292361  461967   411934520324
 26  584722  839829  1356668825821
 27 1169444 1528072  4478273903272

Paul, would you submit the sequences?

Hugo Pfoertner

> 
> SEQUENCE:
> 1,2,3,4,5,6,8,7,10,9,12,16,14,11,13,15,20,18,24,17,32,19,21,
> 28,22,23,26,25,30,40,27,36,48,33,34,64,38,35,42,29,31,56,44,
> 46,39,52,50,45,60,41,43,80,54,37,72,49,51,96,66,68,65,128,
> 
> NAME:
> The power tree (as defined by Knuth), read by rows,
> where T(n,k) is the label of the k-th node in row n.
> 
> COMMENTS:
> The power tree is generated by a systematic method that is supposed
> to give the minimum number of multiplications to arrive at x^n.
> 
> REFERENCES:
> Donald E. Knuth, The Art of Computer Programming Third Edition. Vol. 2,
> Seminumerical Algorithms. Chapter 4.6.3 Evaluation of Powers, Page 464.
> Addison-Wesley, Reading, MA, 1997.
> 
> FORMULA:
> Start the root node with label (1) in row 1.
> Assuming that the first n rows have been constructed,
> define row (n+1) of the power tree as follows.
> Proceeding from left to right in row n of the tree,
> take each node labelled L = T(n,k) and let the labels
> [1, T(2,j_2), T(3,j_3), ..., T(n,j_n)], where j_n=k,
> form the path from the root of the tree to node T(n,k).
> Attach to node (L) new nodes with labels generated by:
> [L+1, L+T(2,j_2), L+T(3,j_3), ..., L+T(n,k)=2*L]
> after discarding any label that has appeared before in the tree.
> 
> EXAMPLE:
> The rows of the power tree begin:
> 1;
> 2;
> 3,4;
> 5,6,8;
> 7,10,9,12,16;
> 14,11,13,15,20,18,24,17,32;
> 19,21,28,22,23,26,25,30,40,27,36,48,33,34,64;
> 38,35,42,29,31,56,44,46,39,52,50,45,60,41,43,80,54,37,72,49,51,96,66,68,6
> 5,128;
> where nodes are attached to each other like so:
> 1->[2];
> 2->[3,4];
> 3->[5,6], 4->[8];
> 5->[7,10], 6->[9,12], 8->[16];
> 7->[14], 10->[11,13,15,20], 9->[18], 12->[24], 16->[32]; ...
> Ex., the path from root node (1) to node (10) is [1,2,3,5,10],
> so the possible labels for nodes to be attached to node (10) are:
> [10+1,10+2,10+3,10+5,10+10]; but label (12) has already been used,
> so 4 nodes with labels [11,13,15,20] are attached to node (10).
> 
> SEE ALSO:
> Cf. A______ (number of nodes in rows), A______ (row sums).
> 
> OFFSET: 1
>