

A114622


The power tree (as defined by Knuth), read by rows, where T(n,k) is the label of the kth node in row n.


12



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;
text;
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. AddisonWesley, Reading, MA, 1997.


LINKS

Alois P. Heinz, Rows n = 1..18, flattened
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]; ...
E.g., 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).


MAPLE

T:= proc(n) option remember; local i, j, l, s; l:= NULL;
for i in [T(n1)] do j:=i; s:=[];
while j>0 do s:= [s[], j]; j:=b(j) od;
for j in sort([s[]]) do
if b(i+j)=0 then b(i+j):=i; l:=l, i+j fi
od
od; l
end: T(1):=1:
b:= proc() 0 end:
seq(T(n), n=1..10); # Alois P. Heinz, Jul 24 2013


MATHEMATICA

T[n_] := T[n] = Module[{i, j, l, s}, l={}; Do[j=i; s={}; While[j>0, AppendTo[s, j]; j = b[j]]; Do[If[b[i+j] == 0, b[i+j]=i; AppendTo[l, i+j]], {j, Sort[s]}], {i, T[n1]}]; l]; T[1]=1; Clear[b]; b[_]=0; Table[T[n], {n, 1, 10}] // Flatten (* JeanFrançois Alcover, Jun 15 2015, after Alois P. Heinz *)


CROSSREFS

Cf. A114623 (number of nodes in rows), A114624 (row sums), A114625 (leftmost node in rows).
See A122352 for another presentation of the tree.
Sequence in context: A334438 A185974 A129129 * A125624 A262388 A297440
Adjacent sequences: A114619 A114620 A114621 * A114623 A114624 A114625


KEYWORD

nonn,tabf,look


AUTHOR

Hugo Pfoertner and Paul D. Hanna, Dec 20 2005


STATUS

approved



