|
%I #6 May 25 2020 05:58:51
%S 77,154,233,293,308,319,359,367,377,382,423,457,466,551,553,559,571,
%T 573,586,616,617,619,623,638,699,713,717,718,734,754,764,813,841,846,
%U 849,869,879,905,914,932,1007,1051,1063,1069,1102,1103,1106,1115,1118,1133
%N 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.
%C 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.
%D 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.
%e 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.
%Y 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].
%K nonn
%O 1,1
%A _Hugo Pfoertner_ and _Neill M. Clift_, Jan 31 2006
|
