|
| |
|
|
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
(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.
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
|
|
|
|
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:
|
|
|
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
|
|
|
CROSSREFS
|
See A122352 for another presentation of the tree.
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
