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

6475341, 13214509, 17900677, 19998021, 25747725, 26429018, 26640937, 27321991, 27404041, 27492775, 27820465, 28475829, 28475875, 28803235, 31947953, 35654893, 35663887, 35801354, 35875087, 38404259, 38860337, 38905477, 39627197, 39995657, 39996042, 40272713, 40468139

Offset

1,1

Comments

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.

Links

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

Example

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

Crossrefs

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

Sequence in context: A209950 A288074 A157787 * A257016 A234090 A344922

Adjacent sequences: A115612 A115613 A115614 * A115616 A115617 A115618

Keyword

nonn

Author

Hugo Pfoertner and Neill M. Clift, Feb 15 2006

Extensions

Extended using the table of length 2^31 at Achim Flammenkamp's web page by Hugo Pfoertner, Sep 06 2015

Status

approved