cp's OEIS Frontend

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.

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