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.
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
Examples
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).
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
- 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
Crossrefs
Programs
-
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 *) -
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
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.
Comments