Services & ResourcesWolfram ForumsMathGroup Archive

[Date Index] [Thread Index] [Author Index]

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