       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
>
> 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=
{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

```

• Prev by Date: How to View Mathematica and Hardcopy Books
• Next by Date: Re: AW: AW: Same scaling for plots/ charts
• Previous by thread: Strange Min/Max result
• Next by thread: Re: Strange Min/Max result