|
Search: id:A113945
|
|
|
| A113945 |
|
Numbers n such that the smallest possible number of multiplications required to compute x^n is by 1 less than the number of multiplications obtained by Knuth's power tree method. |
|
+0
5
|
|
| 77, 154, 233, 293, 308, 319, 359, 367, 377, 382, 423, 457, 466, 551, 553, 559, 571, 573, 586, 616, 617, 619, 623, 638, 699, 713, 717, 718, 734, 754, 764, 813, 841, 846, 849, 869, 879, 905, 914, 932, 1007, 1051, 1063, 1069, 1102, 1103, 1106, 1115, 1118, 1133
(list; graph; listen)
|
|
|
OFFSET
|
1,1
|
|
|
COMMENT
|
The first three terms are given in Knuth's TAOCP, Vol. 2, 3rd Edition, p. 464. The sequence is based on a table of shortest addition chain lengths computed by N. Clift (neillclift(AT)msn.com), see link to A. Flammenkamp's web page given at A003313.
|
|
EXAMPLE
|
a(1)=77 because the power tree construction produces the chain 1 2 3 5 7 14 19 38 76 77 requiring 9 additions, whereas there are 4 shortest chains that come along with 8 additions, e.g. 1 2 4 8 9 17 34 43 77.
|
|
CROSSREFS
|
Cf. A114622 [The power tree (as defined by Knuth)], A003313 [Length of shortest addition chain for n], 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], A115616 [smallest number for which Knuth's power tree method produces an addition chain n terms longer than the shortest possible chain].
Sequence in context: A046435 A004964 A118226 this_sequence A044328 A044709 A075253
Adjacent sequences: A113942 A113943 A113944 this_sequence A113946 A113947 A113948
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Hugo Pfoertner (hugo(AT)pfoertner.org) and N. Clift (neillclift(AT)msn.com), Jan 31 2006
|
|
|
Search completed in 0.002 seconds
|
