A008342 Minimal number of shift, add and subtract operations to multiply by n.

0, 1, 2, 1, 2, 3, 2, 1, 2, 3, 4, 3, 4, 3, 2, 1, 2, 3, 4, 3, 4, 4, 4, 3, 4, 4, 4, 3, 4, 3, 2, 1, 2, 3, 4, 3, 4, 5, 4, 3, 4, 5, 5, 4, 4, 4, 4, 3, 4, 4, 4, 4, 5, 5, 4, 3, 4, 5, 4, 3, 4, 3, 2, 1, 2, 3, 4, 3, 4, 5, 4, 3, 4, 5, 4, 4, 5, 5, 4, 3, 4, 5, 5, 4, 4, 5, 6, 5, 5, 5, 5, 4, 4, 4, 4, 3, 4, 4, 4

Offset

1,3

Links

Doug Grundman and Sean A. Irvine, Table of n, a(n) for n = 1..1024

Sean A. Irvine, Example minimal sequences for n = 1..1024

Example

For n = 7 (a simple case), x8 = x1 << 3, x7 = x8 - x1 for a total of 2 operations.
For n = 22 (requires reusing an expression), x8 = x1 << 3, x7 = x8 - x1, x15 = x7 + x8, x22 = x15 + x7 for a total of 4 operations.
For n = 597 (a tricky case), x4 = x1 << 2, x5 = x4 + x1, x80 = x5 << 4, x85 = x80 + x5, x512 = x1 << 9, x597 = x512 + x85 for a total of 6 operations.

Crossrefs

Sequence in context: A004738 A043554 A005811 * A277214 A278603 A248218

Adjacent sequences: A008339 A008340 A008341 * A008343 A008344 A008345

Keyword

nonn,nice

Author

dg(AT)franklin.com (Doug Grundman)

Status

approved