|
%I #9 May 25 2020 06:00:44
%S 8719,17438,28597,34876,54359,56157,57194,57293,59657,60493,67171,
%T 69752,71017,71065,75799,78865,100987,108503,108718,110361,112093,
%U 112314,112679,113275,114388,114586,115861,119314,119417,120986,133681,133795
%N 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.
%C 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.
%H Hugo Pfoertner, <a href="/A115614/b115614.txt">Table of n, a(n) for n = 1..10000</a>
%e 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].
%Y 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].
%K nonn
%O 1,1
%A _Hugo Pfoertner_ and _Neill M. Clift_, Feb 15 2006
|
