Voozh

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

(list; graph; refs; listen; history; text; internal format)

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)