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.

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

Offset

1,1

Comments

The first three terms are given in Knuth's TAOCP, Vol. 2. The sequence is based on a table of shortest addition chain lengths computed by Neill M. Clift, see link to Achim Flammenkamp's web page given at A003313.

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

Table of n, a(n) for n=1..50.

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: A227932 A004964 A118226 * A044328 A044709 A338189

Adjacent sequences: A113942 A113943 A113944 * A113946 A113947 A113948

Keyword

nonn

Author

Hugo Pfoertner and Neill M. Clift, Jan 31 2006

Status

approved