Neill M. Clift - cp's OEIS frontend

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

77, 154, 233, 293, 308, 319, 359, 367, 377, 382, 423, 457, 466, 551, 553, 559, 571, 573, 586, 616, 617, 619, 623, 638, 699, 713, 717, 718, 734, 754, 764, 813, 841, 846, 849, 869, 879, 905, 914, 932, 1007, 1051, 1063, 1069, 1102, 1103, 1106, 1115, 1118, 1133

Offset: 1

Hugo Pfoertner and Neill M. Clift, Jan 31 2006

nonn

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.

			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.

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.

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

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.

Original entry on oeis.org

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

Hugo Pfoertner and Neill M. Clift, Feb 15 2006

nonn

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.

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

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

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

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.

Original entry on oeis.org

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

Hugo Pfoertner and Neill M. Clift, Feb 15 2006

nonn

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.

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

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

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

A115616 Smallest number for which Knuth's power tree method produces an addition chain n terms longer than the shortest possible chains for this number.

Original entry on oeis.org

77, 8719, 6475341

Offset: 1

Hugo Pfoertner and Neill M. Clift, Feb 15 2006

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.

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], A115615 [numbers such that Knuth's power tree method produces a result deficient by 3].

cp's OEIS Frontend

User: Neill M. Clift

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

Views

Author

Keywords

Comments

Examples

References

Crossrefs

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

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.

Views

Author

Keywords

Comments

Examples

Crossrefs

Extensions

A115616 Smallest number for which Knuth's power tree method produces an addition chain n terms longer than the shortest possible chains for this number.

Views

Author

Keywords

Comments

Crossrefs