|
|
A186520
|
|
Number of evaluation schemes for x^n achieving the minimal number of multiplications, and with the maximal number of squarings among the multiplications.
|
|
0
|
|
|
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
|
|
|
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
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|