login
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.
13
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
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.
The number of multiplications required to compute x^m by this method is n-1 if m appears in the n-th row. The smallest number m for which the power tree method does not give the minimum number of multiplications for x^m is m = 77 (see A113945, Knuth reference, or Pfoertner link "Addition chains"). The power tree method requires 9 multiplications for x^77 but A003313(77) = 8. - Pontus von Brömssen, Apr 23 2024
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];
...
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(n-1)] 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[n-1]}]; l]; T[1]=1; Clear[b]; b[_]=0; Table[T[n], {n, 1, 10}] // Flatten (* Jean-François Alcover, Jun 15 2015, after Alois P. Heinz *)
PROG
(Python)
from functools import cache
b = dict()
@cache
def T(n):
global b
if n == 1: return [1]
l = []
for i in T(n-1):
j = i; s = []
while j > 0:
s.append(j)
j = b.get(j, 0)
for j in sorted(s):
if b.get(i+j, 0) == 0:
b[i+j] = i
l.append(i+j)
return l
print([Tik for i in range(1, 9) for Tik in T(i)]) # Michael S. Branicky, Apr 28 2024 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 A366948
KEYWORD
nonn,tabf,look
AUTHOR
Hugo Pfoertner and Paul D. Hanna, Dec 20 2005
STATUS
approved