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

8719, 17438, 28597, 34876, 54359, 56157, 57194, 57293, 59657, 60493, 67171, 69752, 71017, 71065, 75799, 78865, 100987, 108503, 108718, 110361, 112093, 112314, 112679, 113275, 114388, 114586, 115861, 119314, 119417, 120986, 133681, 133795

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

Hugo Pfoertner, Table of n, a(n) for n = 1..10000

Example

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

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], 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: A233679 A266578 A031852 * A165630 A250999 A214171

Adjacent sequences: A115611 A115612 A115613 * A115615 A115616 A115617

Keyword

nonn

Author

Hugo Pfoertner and Neill M. Clift, Feb 15 2006

Status

approved