

A008342


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


1



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



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



