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.
Original entry on oeis.org
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
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).
- 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.
See
A122352 for another presentation of the tree.
-
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
-
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 *)
-
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
A115614
Numbers n such that the smallest possible number of multiplications required to compute x^n is by 2 less than the number of multiplications obtained by Knuth's power tree method.
Original entry on oeis.org
8719, 17438, 28597, 34876, 54359, 56157, 57194, 57293, 59657, 60493, 67171, 69752, 71017, 71065, 75799, 78865, 100987, 108503, 108718, 110361, 112093, 112314, 112679, 113275, 114388, 114586, 115861, 119314, 119417, 120986, 133681, 133795
Offset: 1
a(1)=8719 because this is the smallest number for which the addition chain produced by the power tree method [1 2 3 5 7 14 28 56 61 117 234 468 936 1872 3744 3861 7722 7783 8719] is by two terms longer than the shortest possible chains for this number. An example of such a chain is [1 2 3 6 9 15 17 34 68 136 272 544 1088 2176 4352 4367 8719].
Cf.
A114622 [The power tree (as defined by Knuth)],
A003313 [Length of shortest addition chain for n],
A113945 [numbers such that Knuth's power tree method produces a result deficient by 1],
A115615 [numbers such that Knuth's power tree method produces a result deficient by 3],
A115616 [smallest number for which Knuth's power tree method produces an addition chain n terms longer than the shortest possible chain].
A115615
Numbers n such that the smallest possible number of multiplications required to compute x^n is by 3 less than the number of multiplications obtained by Knuth's power tree method.
Original entry on oeis.org
6475341, 13214509, 17900677, 19998021, 25747725, 26429018, 26640937, 27321991, 27404041, 27492775, 27820465, 28475829, 28475875, 28803235, 31947953, 35654893, 35663887, 35801354, 35875087, 38404259, 38860337, 38905477, 39627197, 39995657, 39996042, 40272713, 40468139
Offset: 1
a(1)=6475341 because this is the smallest number for which the addition chain produced by the power tree method [1 2 3 5 7 14 19 38 76 79 158 316 632 1264 2528 5056 5063 10119 12647 25294 50588 101176 202352 404704 809408 809427 1618835 3237670 6475340 6475341] is by three terms longer than the shortest possible chains for this number. An example of such a chain is [1 2 4 8 16 32 64 65 129 258 387 774 1548 1613 3161 6322 12644 25288 50576 101152 202304 404608 809216 1618432 3236864 3238477 6475341].
Cf.
A114622 [The power tree (as defined by Knuth)],
A003313 [Length of shortest addition chain for n],
A113945 [numbers such that Knuth's power tree method produces a result deficient by 1],
A115614 [numbers such that Knuth's power tree method produces a result deficient by 2],
A115616 [smallest number for which Knuth's power tree method produces an addition chain n terms longer than the shortest possible chain].
A115616
Smallest number for which Knuth's power tree method produces an addition chain n terms longer than the shortest possible chains for this number.
Original entry on oeis.org
77, 8719, 6475341
Offset: 1
Cf.
A114622 [The power tree (as defined by Knuth)],
A003313 [Length of shortest addition chain for n],
A113945 [numbers such that Knuth's power tree method produces a result deficient by 1],
A115614 [numbers such that Knuth's power tree method produces a result deficient by 2],
A115615 [numbers such that Knuth's power tree method produces a result deficient by 3].
A115617
Smallest number for which Knuth's power tree method produces an addition chain of length n.
Original entry on oeis.org
1, 2, 3, 5, 7, 11, 19, 29, 47, 71, 127, 191, 319, 551, 1007, 1711, 2687, 4703, 8447, 15179, 28079, 45997, 89599, 138959, 257513, 485657, 834557, 1433501, 2854189, 4726127, 8814047, 15692153, 30078877, 53574623, 94189807, 177848059, 322928189
Offset: 0
Cf.
A114622 (the power tree (as defined by Knuth)),
A003064 (smallest number with addition chain of length n),
A113945 (numbers such that Knuth's power tree method produces a result deficient by 1).
A383329
Number of multiplications required to compute x^n by Knuth's power tree method.
Original entry on oeis.org
0, 1, 2, 2, 3, 3, 4, 3, 4, 4, 5, 4, 5, 5, 5, 4, 5, 5, 6, 5, 6, 6, 6, 5, 6, 6, 6, 6, 7, 6, 7, 5, 6, 6, 7, 6, 7, 7, 7, 6, 7, 7, 7, 7, 7, 7, 8, 6, 7, 7, 7, 7, 8, 7, 8, 7, 8, 8, 8, 7, 8, 8, 8, 6, 7, 7, 8, 7, 8, 8, 9, 7, 8, 8, 8, 8, 9, 8, 9, 7, 8, 8, 8, 8, 8, 8, 9
Offset: 1
- Donald E. Knuth, The Art of Computer Programming, Vol. 2, 3rd edition, Addison-Wesley, 1998. See page 464.
Showing 1-6 of 6 results.
Comments