Christophe Mouilleron - cp's OEIS frontend

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

Laurent Thévenoux and Christophe Mouilleron, Feb 23 2011

nonn

			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.

Cf A003313, A186435, A186437.

A186437 Maximal number of squarings in an evaluation scheme for x^n achieving the minimal number of operations.

Original entry on oeis.org

0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 3, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 4, 5, 5, 5, 4, 5, 5, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5

Offset: 1

Laurent Thévenoux and Christophe Mouilleron, Feb 23 2011

nonn

a(n) is also the maximal number of doublings in a shortest addition chain for n.

			For n=5, we can evaluate x^5 using only 3 operations in 2 ways:
  x^2 = (x)^2; x^3 = x * x^2; x^5 = x^2 * x^3
  x^2 = (x)^2; x^4 = (x^2)^2; x^5 = x * x^4
The second way achieves the maximal number of doublings, which is a(5) = 2.

Cf A003313.

We have a(n) = floor(log_2(n)) for all n ≤ 60 except 23, 39, 43 and 46.

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

Original entry on oeis.org

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

Laurent Thevenoux and Christophe Mouilleron, Feb 23 2011

nonn

			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

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).

A173157 a(n) is the number of ways to evaluate a bivariate polynomial of the form p(T,X) = p00 + T * q(X) where q(X) is an univariate polynomial of degree n. Each addition or multiplication takes exactly two arguments, and two parenthesizations which are equal modulo commutativity are considered as a unique way to evaluate p(T,X).

Original entry on oeis.org

1, 10, 481, 88384, 57363910, 122657263474, 829129658616013, 17125741272619781635, 1055157310305502607244946, 190070917121184028045719056344, 98543690848554380947490522591191672

Offset: 0

Christophe Mouilleron, Feb 11 2010

nonn

			For example, there are 10 ways of evaluating p00 + T * (p10 + p11 * X):
p00 + ((p10*T) + (p11*(X*T)))
p00 + ((p10*T) + ((p11*T)*X))
p00 + ((p10*T) + ((p11*X)*T))
p00 + (p10 + (p11*X)) * T
(p00 + (p10*T)) + (p11*(X*T))
(p00 + (p10*T)) + ((p11*T)*X)
(p00 + (p10*T)) + ((p11*X)*T)
(p00 + (p11*(X*T))) + (p10*T)
(p00 + ((p11*T)*X)) + (p10*T)
(p00 + ((p11*X)*T)) + (p10*T)

Guillaume Revy, Implementation of binary floating-point arithmetic on embedded integer processors, Ph D Thesis, University Lyon - ENS Lyon, December 2009, Table 6.2 in Section 6.1.6

This generalizes A169608.

cparen := proc(e)
local i, l, s, a, b, pa, pb, la, ee, e1, v, t, g;
option remember;
if type(e, name) then 1
elif type(e, `+`) then
s := 0; ee := convert(e, list); e1 := ee[1]; ee := subsop(1=NULL, ee);
for i from 0 to nops(ee)-1 do
for la in combinat[choose](ee, i) do
a := e1+convert(la, `+`); b := e-a; pa := procname(a); pb := procname(b); s := s + pa * pb;
od
od;
g := 0;
for a in e while g<>1 do g:=gcd(g, a) od;
if g=1 then g:=[] elif type(g, `*`) then g:=convert(g, list) else g:=[g] fi;
g := map(proc(t) if type(t, `^`) then op(1, t)$op(2, t) else t fi end, g);
for i from 1 to nops(g) do
for v in combinat[choose](g, i) do
a := convert(v, `*`); t := expand(e/a); s := s + procname(a)*procname(t);
od
od;
s
elif type(e, `*`) or type(e, `^`) then
s := 0;
if type(e, `*`) then ee := convert(e, list) else ee:=[e] fi;
ee := map(proc(t) if type(t, `^`) then op(1, t)$op(2, t) else t fi end, ee);
for i from 1 to iquo(nops(ee), 2) do
for la in combinat[choose](ee, i) do
a := convert(la, `*`); b := e/a;
if 2*i=nops(ee) and op(1, {a, b})<>a then next fi;
if a=b then s := s + (procname(a) * (1+procname(a))) / 2;
else s := s + procname(a)*procname(b);
fi
od
od;
s
else ERROR("unexpected type", whattype(e), e)
fi
end:
f := proc(n) local i; cparen(a[0,0] + add(a[1,i]*T*X^i, i=0..n)) end:

A169608 a(n) is the number of ways to evaluate a polynomial of degree n, say p0 + p1x + ... + pnx^n, where each addition or multiplication takes exactly two arguments.

Original entry on oeis.org

1, 1, 7, 163, 11602, 2334244, 1304066578, 1972869433837, 8012682343669366, 86298937651093314877, 2449381767217281163362301

Offset: 0

Christophe Mouilleron, Dec 03 2009, Jan 23 2010

			For example, there are 7 ways to evaluate a polynomial of degree 2:
((a0+(x*a1))+(x*(x*a2)))
((a0+(x*a1))+((x*x)*a2))
(a0+(x*(a1+(x*a2))))
(a0+((x*a1)+(x*(x*a2))))
(a0+((x*a1)+((x*x)*a2)))
((x*a1)+(a0+(x*(x*a2))))
((x*a1)+(a0+((x*x)*a2)))

Guillaume Revy, Implementation of binary floating-point arithmetic on embedded integer processors, Ph D Thesis, University Lyon - ENS Lyon, December 2009, Table 6.1 in Section 6.1.6

cparen := proc(e)
local i, l, s, a, b, pa, pb, la, ee, e1, v, t, g;
option remember;
if type(e, name) then 1
elif type(e, `+`) then
s := 0; ee := convert(e, list); e1 := ee[1]; ee := subsop(1=NULL, ee);
for i from 0 to nops(ee)-1 do
for la in combinat[choose](ee, i) do
a := e1+convert(la, `+`); b := e-a; pa := procname(a); pb := procname(b); s := s + pa * pb;
od
od;
g := 0;
for a in e while g<>1 do g:=gcd(g, a) od;
if g=1 then g:=[] elif type(g, `*`) then g:=convert(g, list) else g:=[g] fi;
g := map(proc(t) if type(t, `^`) then op(1, t)$op(2, t) else t fi end, g);
for i from 1 to nops(g) do
for v in combinat[choose](g, i) do
a := convert(v, `*`); t := expand(e/a); s := s + procname(a)*procname(t);
od
od;
s
elif type(e, `*`) or type(e, `^`) then
s := 0;
if type(e, `*`) then ee := convert(e, list) else ee:=[e] fi;
ee := map(proc(t) if type(t, `^`) then op(1, t)$op(2, t) else t fi end, ee);
for i from 1 to iquo(nops(ee), 2) do
for la in combinat[choose](ee, i) do
a := convert(la, `*`); b := e/a;
if 2*i=nops(ee) and op(1, {a, b})<>a then next fi;
if a=b then s := s + (procname(a) * (1+procname(a))) / 2;
else s := s + procname(a)*procname(b);
fi
od
od;
s
else ERROR("unexpected type", whattype(e), e)
fi
end:
A169608 := proc(n) cparen(sum(p[i] * x^i, i=0..n)); end:

Author's name changed by N. J. A. Sloane, Dec 17 2009, at the request of Paul Zimmermann
Minor editing of definition by N. J. A. Sloane, Dec 19 2009
Add a(7) to a(10) Christophe Mouilleron, Jan 04 2010

cp's OEIS Frontend

User: Christophe Mouilleron

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

Views

Author

Keywords

Examples

Crossrefs

A186437 Maximal number of squarings in an evaluation scheme for x^n achieving the minimal number of operations.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

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

Views

Author

Keywords

Examples

Crossrefs

Views

Author

Keywords

Examples

References

Crossrefs

Programs

Maple

A169608 a(n) is the number of ways to evaluate a polynomial of degree n, say p0 + p1x + ... + pnx^n, where each addition or multiplication takes exactly two arguments.

Views

Author

Keywords

Examples

References

Programs

Maple

Extensions

cp's OEIS Frontend

User: Christophe Mouilleron

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

Views

Author

Keywords

Examples

Crossrefs

A186437 Maximal number of squarings in an evaluation scheme for x^n achieving the minimal number of operations.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

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

Views

Author

Keywords

Examples

Crossrefs

Views

Author

Keywords

Examples

References

Crossrefs

Programs

Maple

A169608 a(n) is the number of ways to evaluate a polynomial of degree n, say p0 + p1*x + ... + pn*x^n, where each addition or multiplication takes exactly two arguments.

Views

Author

Keywords

Examples

References

Programs

Maple

Extensions

A169608 a(n) is the number of ways to evaluate a polynomial of degree n, say p0 + p1x + ... + pnx^n, where each addition or multiplication takes exactly two arguments.