|
| |
|
|
A114622
|
|
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.
|
|
10
| |
|
|
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
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 1,2
|
|
|
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
| 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.
|
|
|
LINKS
| 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
|
|
|
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 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.
|
|
|
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,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).
|
|
|
CROSSREFS
| 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: A078840 A185974 A129129 * A125624 A145518 A130916
Adjacent sequences: A114619 A114620 A114621 * A114623 A114624 A114625
|
|
|
KEYWORD
| nonn,tabf
|
|
|
AUTHOR
| Hugo Pfoertner (hugo(AT)pfoertner.org) and Paul D. Hanna (pauldhanna(AT)juno.com), Dec 20 2005
|
| |
|
|
