A186435 Number of evaluation schemes for x^n achieving the minimal number of multiplications.

1, 1, 1, 1, 2, 2, 6, 1, 3, 4, 19, 3, 10, 16, 4, 1, 2, 7, 37, 6, 31, 48, 4, 4, 14, 24, 5, 26, 152, 12, 80, 1, 2, 4, 51, 12, 39, 100, 20, 8, 23, 90, 4, 81, 14, 8, 242, 5, 12, 36, 4, 38, 215, 16, 172, 36, 190, 395, 40, 24

Offset

1,5

Links

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

Example

For n=7, we can evaluate x^7 using only 4 multiplications in 6 ways:
x^2 = x * x ; x^3 = x   * x^2 ; x^4 = x   * x^3 ; x^7 = x^3 * x^4
x^2 = x * x ; x^3 = x   * x^2 ; x^4 = x^2 * x^2 ; x^7 = x^3 * x^4
x^2 = x * x ; x^3 = x   * x^2 ; x^5 = x^2 * x^3 ; x^7 = x^2 * x^5
x^2 = x * x ; x^3 = x   * x^2 ; x^6 = x^3 * x^3 ; x^7 = x   * x^6
x^2 = x * x ; x^4 = x^2 * x^2 ; x^5 = x   * x^4 ; x^7 = x^2 * x^5
x^2 = x * x ; x^4 = x^2 * x^2 ; x^6 = x^2 * x^4 ; x^7 = x   * x^6

Crossrefs

See A003313 for the minimal number of multiplications to evaluate x^n.

See A001190 for the total number of evaluation schemes for x^n (regardless of the number of effective multiplications).

A079300 gives the number of minimal chains (= sequences of powers of x) ending at x^n. This is actually a bit less than the number of evaluation schemes since two schemes may produce the same chain, like the first and second schemes in the example above, where the corresponding chain is (x^2, x^3, x^4, x^7).

Sequence in context: A199220 A047916 A101207 * A260297 A199476 A209124

Adjacent sequences: A186432 A186433 A186434 * A186436 A186437 A186438

Keyword

nonn

Author

Laurent Thevenoux and Christophe Mouilleron, Feb 23 2011

Status

approved