|
%I #29 Apr 28 2024 11:40:26
%S 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,
%T 26,25,30,40,27,36,48,33,34,64,38,35,42,29,31,56,44,46,39,52,50,45,60,
%U 41,43,80,54,37,72,49,51,96,66,68,65,128
%N 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.
%C The power tree is generated by a systematic method that is supposed to give the minimum number of multiplications to arrive at x^n.
%C 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
%D 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.
%H Alois P. Heinz, <a href="/A114622/b114622.txt">Rows n = 1..18, flattened</a>
%H Hugo Pfoertner, <a href="http://www.randomwalk.de/sequences/pwrtree.txt">Fortran program implementing Knuth's algorithm</a>, from "Answers to exercises" for Section 4.6.3 page 692, exercise 5, page 481 TAOCP Vol. 2.
%H Hugo Pfoertner, <a href="/A003313/a003313.txt">Addition chains</a>
%F 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.
%e The rows of the power tree begin:
%e 1;
%e 2;
%e 3,4;
%e 5,6,8;
%e 7,10,9,12,16;
%e 14,11,13,15,20,18,24,17,32;
%e 19,21,28,22,23,26,25,30,40,27,36,48,33,34,64;
%e 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;
%e where nodes are attached to each other as follows:
%e 1->[2];
%e 2->[3,4];
%e 3->[5,6], 4->[8];
%e 5->[7,10], 6->[9,12], 8->[16];
%e 7->[14], 10->[11,13,15,20], 9->[18], 12->[24], 16->[32];
%e ...
%e 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).
%p T:= proc(n) option remember; local i, j, l, s; l:= NULL;
%p for i in [T(n-1)] do j:=i; s:=[];
%p while j>0 do s:= [s[], j]; j:=b(j) od;
%p for j in sort([s[]]) do
%p if b(i+j)=0 then b(i+j):=i; l:=l, i+j fi
%p od
%p od; l
%p end: T(1):=1:
%p b:= proc() 0 end:
%p seq(T(n), n=1..10); # _Alois P. Heinz_, Jul 24 2013
%t 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_ *)
%o (Python)
%o from functools import cache
%o b = dict()
%o @cache
%o def T(n):
%o global b
%o if n == 1: return [1]
%o l = []
%o for i in T(n-1):
%o j = i; s = []
%o while j > 0:
%o s.append(j)
%o j = b.get(j, 0)
%o for j in sorted(s):
%o if b.get(i+j, 0) == 0:
%o b[i+j] = i
%o l.append(i+j)
%o return l
%o print([Tik for i in range(1, 9) for Tik in T(i)]) # _Michael S. Branicky_, Apr 28 2024 after _Alois P. Heinz_
%Y Cf. A114623 (number of nodes in rows), A114624 (row sums), A114625 (leftmost node in rows).
%Y See A122352 for another presentation of the tree.
%Y Cf. A003313, A113945.
%K nonn,tabf,look,changed
%O 1,2
%A _Hugo Pfoertner_ and _Paul D. Hanna_, Dec 20 2005
|
