1,2

The power tree is generated by a systematic method that is supposed to give the minimum number of multiplications to arrive at x^n.

D. 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.

Hugo Pfoertner, Fortran program implementing Knuth's algorithm, from "Answers to exercises" for Section 4.6.3 page 692, exercise 5, page 481 TAOCP Vol. 2.

Hugo Pfoertner, Addition chains

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 labeled 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.

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,65,128;

where nodes are attached to each other as follows:

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

Cf. A114623 (number of nodes in rows), A114624 (row sums), A114625 (left-most node in rows).

See A122352 for another presentation of the tree.

Sequence in context: A117333 A078840 A129129 this_sequence A125624 A145518 A003965

Adjacent sequences: A114619 A114620 A114621 this_sequence A114623 A114624 A114625

nonn,tabf

Hugo Pfoertner (hugo(AT)pfoertner.org) and Paul D. Hanna (pauldhanna(AT)juno.com), Dec 20 2005