login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 12
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.

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

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 *)

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 A297440

Adjacent sequences:  A114619 A114620 A114621 * A114623 A114624 A114625

KEYWORD

nonn,tabf,look

AUTHOR

Hugo Pfoertner and Paul D. Hanna, Dec 20 2005

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 27 19:34 EDT 2021. Contains 347694 sequences. (Running on oeis4.)