%I #13 May 25 2020 06:08:07

%S 6475341,13214509,17900677,19998021,25747725,26429018,26640937,

%T 27321991,27404041,27492775,27820465,28475829,28475875,28803235,

%U 31947953,35654893,35663887,35801354,35875087,38404259,38860337,38905477,39627197,39995657,39996042,40272713,40468139

%N 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.

%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.

%e 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].

%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], 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].

%K nonn

%O 1,1

%A _Hugo Pfoertner_ and _Neill M. Clift_, Feb 15 2006

%E Extended using the table of length 2^31 at _Achim Flammenkamp_'s web page by _Hugo Pfoertner_, Sep 06 2015