%I #11 Aug 21 2022 22:26:58
%S 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,
%T 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,
%U 12
%N Number of evaluation schemes for x^n achieving the minimal number of multiplications, and with the maximal number of squarings among the multiplications.
%e For n=7, we can evaluate x^7 using only 4 operations in 6 ways:
%e x^2 = x * x ; x^3 = x * x^2 ; x^4 = x * x^3 ; x^7 = x^3 * x^4 (1 squaring)
%e x^2 = x * x ; x^3 = x * x^2 ; x^4 = x^2 * x^2 ; x^7 = x^3 * x^4 (2 squarings)
%e x^2 = x * x ; x^3 = x * x^2 ; x^5 = x^2 * x^3 ; x^7 = x^2 * x^5 (1 squaring)
%e x^2 = x * x ; x^3 = x * x^2 ; x^6 = x^3 * x^3 ; x^7 = x * x^6 (2 squarings)
%e x^2 = x * x ; x^4 = x^2 * x^2 ; x^5 = x * x^4 ; x^7 = x^2 * x^5 (2 squarings)
%e x^2 = x * x ; x^4 = x^2 * x^2 ; x^6 = x^2 * x^4 ; x^7 = x * x^6 (2 squarings)
%e The maximal number of squarings in these evaluation schemes is 2, and it is achieved by a(7) = 4 schemes.
%Y Cf A003313, A186435, A186437.
%K nonn
%O 1,6
%A Laurent Thévenoux and _Christophe Mouilleron_, Feb 23 2011
|