login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 3
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 (list; graph; refs; listen; history; text; internal format)
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 19 09:16 EST 2022. Contains 350464 sequences. (Running on oeis4.)