Re: Strange Min/Max result

*To*: mathgroup at smc.vnet.net*Subject*: [mg62328] Re: [mg62324] Strange Min/Max result*From*: Andrzej Kozlowski <akoz at mimuw.edu.pl>*Date*: Mon, 21 Nov 2005 03:54:12 -0500 (EST)*References*: <200511200419.XAA28569@smc.vnet.net>*Sender*: owner-wri-mathgroup at wolfram.com

On 20 Nov 2005, at 13:19, neillclift at msn.com wrote: > While playing with a equation for addition chains I wanted to > manipulate something like this: > > n = 2i + Sum[Min[i - j, 2^(d - r + 1 - j)], {j, 0, r - 3}] > > Now Mathematica doesn't seem to be able to do much with equations like > this. > I had no clue but Mathematica knows much more than me. I happened > to be > flipping > though The Mathematica Guidebook for Symbolics and saw this being > used: > > max[x_, y_] := 1/2(x + y + Sqrt[(x - y)^2]) > > Very smart. So I thought I could do: > > min1[x_, y_] := 1/2(x + y - Sqrt[(x - y)^2]) > > This gives the wrong results though: > > n = 2i + Sum[min1[i - j, 2^(d - r + 1 - j)], {j, 0, r - 3}] > > n = 2^(2+d-2r)(-4+2^r) + 2i > > I can see its wrong with something like this: > > n = 2i + Sum[min1[ > i - j, 2^(d - r + 1 - j)], {j, > 0, r - 3}] /. d -> 8 /. r -> 4 /. i -> 16 > n = 80 > > The real answer is > n = 2i + Sum[Min[ > i - j, 2^(d - r + 1 - j)], {j, > 0, r - 3}] /. d -> 8 /. r -> 4 /. i -> 16 > n = 63 > > So whats going on here and is there any way to manipulate equations > with Min and Max in them? > Thanks. > Neill. > First of all, all that Mathematica actually computed above is this: 2*i + Sum[2^(d - r + 1 - j), {j, 0, r - 3}] 2^(d - 2*r + 2)*(-4 + 2^r) + 2*i Of course this is true only if 2^(d - r + 1 - j) <= i - j for all j. It looks like Mathematica made a very strong assumption in order to give an answer here. I am not sure if this should be considered a "bug' since the alternative is surely to give no answer at all. I don't believe Mathematica will be able to give you any "closed' formula for the general solution. In fact, I think if you consider carefully your sum you will see that no such formula can be given, at least without introducing some special notation. To see what I mean let's analyse the problem a little closer. What I will do is "solve" the problem by hand making certain assumptions. Cases that do not satisfy the assumptions can be easily settled separately. So what I want to do is to find the sum: Sum[Min[i - j, 2^(d - r + 1 - j)], {j, 0, k}] under the assumption that i>k. The reason why it is reasonable to make this assumption is that Min[i - j, 2^(d - r + 1 - j)] , 2^(d - r + 1 - j) is always positive, so as soon as i<j the minimum is 2^(d - r + 1 - j). So if i <k then we can split the sum into two parts, one of which is easy to sum and the other is of the form we are looking for. Next, let us also assume that i < 2^(d - r + 1 ). The reason is that for x>=1, if x >= y then x-1>=y/2 so if i-j >= 2^(d - r + 1 - j) then i-j-1>=2^(d - r + 1 - j-1) and so on. So again this case can be dealt with easily. So now we can simply split the sum into two sub-sums, where we have Min[i - j, 2^(d - r + 1 - j)] = i -j for j between 0 and p and Min[i - j, 2^(d - r + 1 - j)] = 2^(d - r + 1 - j) for j between p and k, where p is the largest integer less than or equal to the solution of the transcendental equation i - z == 2^(d - r + 1 - z) Thus the answer is the sum of two expressions: f = Simplify[Sum[i - j, {j, 0, p}]] (1/2)*(2*i - p)*(p + 1) and g = Simplify[Sum[2^(d - r + 1 - j), {j, p + 1, r - 3}]] 2^(d - p - 2*r + 1)*(-2^(p + 3) + 2^r) hence it is: sol = Simplify[f + g] -(p^2/2) - p/2 + 2^(d - 2*r + 1)*(-8 + 2^(r - p)) + i*(p + 1) Of course this integer p has to be found numerically, as there can be no closed form solution to this transcendental equation. This is why I am pretty sure Mathematica will not be able to give one. Finally, let's check all this on a case that satisfies the conditions that we imposed. Let's choose values of the parameters: {r, i, d} = {10, 8, 15}; Let's check our conditions: i>r-3 True i < 2^(d - r + 1 ) True The transcendental equation that needs to be solve takes the form: i - z == 2^(d - r + 1 - z) 8 - z == 2^(6 - z) We can actually guess the solution but let's use FindRoot anyway: FindRoot[8 - z == 2^(6 - z), {z, 1}] Out[71]= {z -> 4.} Let's now set p = 4; and compare the value of our expression sol: sol 67/2 with the value of the sum: Sum[Min[i - j, 2^(d - r + 1 - j)], {j, 0, r - 3}] 67/2 Andrzej Kozlowski

**References**:**Strange Min/Max result***From:*neillclift@msn.com

**How to View Mathematica and Hardcopy Books**

**Re: AW: AW: Same scaling for plots/ charts**

**Strange Min/Max result**

**Re: Strange Min/Max result**