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

Author

Laurent Thévenoux and Christophe Mouilleron, Feb 23 2011

Keywords

• nonn

Examples

			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.