A186520 Number of evaluation schemes for x^n achieving the minimal number of multiplications, and with the maximal number of squarings among the multiplications.

1, 1, 1, 1, 1, 2, 4, 1, 1, 2, 4, 3, 5, 10, 2, 1, 1, 2, 4, 3, 5, 10, 2, 4, 7, 12, 2, 16, 47, 6, 22, 1, 1, 2, 4, 3, 5, 10, 10, 4, 6, 12, 2, 18, 2, 4, 10, 5, 7, 17, 2, 19, 55, 6, 28, 22, 49, 120, 8, 12

Offset

1,6

Links

Table of n, a(n) for n=1..60.

Example

For n=7, we can evaluate x^7 using only 4 operations in 6 ways:
  x^2 = x * x ; x^3 = x   * x^2 ; x^4 = x   * x^3 ; x^7 = x^3 * x^4    (1 squaring)
  x^2 = x * x ; x^3 = x   * x^2 ; x^4 = x^2 * x^2 ; x^7 = x^3 * x^4    (2 squarings)
  x^2 = x * x ; x^3 = x   * x^2 ; x^5 = x^2 * x^3 ; x^7 = x^2 * x^5    (1 squaring)
  x^2 = x * x ; x^3 = x   * x^2 ; x^6 = x^3 * x^3 ; x^7 = x   * x^6    (2 squarings)
  x^2 = x * x ; x^4 = x^2 * x^2 ; x^5 = x   * x^4 ; x^7 = x^2 * x^5    (2 squarings)
  x^2 = x * x ; x^4 = x^2 * x^2 ; x^6 = x^2 * x^4 ; x^7 = x   * x^6    (2 squarings)
The maximal number of squarings in these evaluation schemes is 2, and it is achieved by a(7) = 4 schemes.

Crossrefs

Cf A003313, A186435, A186437.

Sequence in context: A188348 A336434 A007738 * A158570 A295224 A074749

Adjacent sequences: A186517 A186518 A186519 * A186521 A186522 A186523

Keyword

nonn

Author

Laurent Thévenoux and Christophe Mouilleron, Feb 23 2011

Status

approved