1
$\begingroup$

As suggested there, here is a copy of the question I've posted on Math.Stackexchange.

Suppose we want to count the number of instructions executed by the following Python code:

sum = 1
print("1 instruction first")

for i in range(1,n+1):
    for j in range(i,n-3+1):
        sum = sum + i + j 
        print(f"3 instructions here : {i}, {j}")

Trivially, for n = 5 (for example), we can count 10 instructions (1 instruction for the first line, and 3 instructions to compute the sum):

1 instruction first
3 instructions here : 1, 1
3 instructions here : 1, 2
3 instructions here : 2, 2

Let us try to evaluate this mathematically. The number of instructions is given by the following expression: $1 + \sum_{i=1}^{n} \sum_{j=i}^{n-3} 3$

Mathematica (or at least WolframAlpha) evaluates this expression as $\frac{3}{2} (n - 5) n + 1$... which is equal to $1$ for $n=5$. Indeed this closed formula doesn't take into account the fact that by convention, an empty sum (when the start index of the variable is greater than the upper bound) sums to 0.

So, three questions:

  1. did I make a mistake in my reasoning?
  2. is there a bug in Mathematica (I mean, with respect to what I exposed there)?
  3. how to correctly express the for loops with sums in that case?
$\endgroup$
7
  • 4
    $\begingroup$ Please show the actual Mathematica code you used. $\endgroup$
    – bbgodfrey
    Jun 30, 2021 at 13:28
  • $\begingroup$ As I said, I just used WolframAlpha ; the formula I used is : 1 + sum_(i=1)^n sum_(j=i)^(n-3) n $\endgroup$
    – Greg82
    Jun 30, 2021 at 15:00
  • 1
    $\begingroup$ @Greg82 Wolfram|Alpha is not Mathematica and the idea that Mathematica would do the same thing as W|A is a misconception. In fact, W|A is off-topic here. $\endgroup$
    – Szabolcs
    Jun 30, 2021 at 15:11
  • $\begingroup$ @Szabolcs, sorry for this misconception, I followed the suggestion given in math.stackexchange to post it here (are WolframAlpha and Mathematica engines really different, by the way?). Edit: Answers given below seem to confirm that Mathematica has the same behaviour for my question $\endgroup$
    – Greg82
    Jun 30, 2021 at 15:16
  • 2
    $\begingroup$ I answered here, but briefly: 1 + Sum[3, {j, 1, n - 3}, {i, 1, j}] is what you should have evaluated instead. $\endgroup$ Jun 30, 2021 at 19:42

2 Answers 2

2
$\begingroup$

tl;dr I would consider this a bug, although not a surprising one.


This is how one would normally write this sum in Mathematica:

1 + Sum[3, {i, n}, {j, i, n - 3}]

To keep things simple, I will use the following simplified version:

Sum[1, {i, n}, {j, i, n - 3}]
(* 1/2 (-5 n + n^2) *)

As you observe, the result is not correct for symbolic n. For an explicit integer n, it does give the correct result as it performs the summation explicitly:

With[{n = 5},
 Sum[1, {i, n}, {j, i, n - 3}]
]
(* 3 *)

Most likely, Mathematica computes this sum as

Sum[Sum[1, {j, i, n - 3}], {i, n}]

The result of the inner one is

Sum[1, {j, i, n - 3}]
(* -2 - i + n *)

This result is valid only when i <= n-3, as you also note in the question. This behaviour is normal and documented for Sum, though perhaps difficult to notice on the documentation page. There is an option to ask Sum to generate explicit conditions for when the result is valid:

Sum[1, {j, i, n - 3}, GenerateConditions -> True]
(* ConditionalExpression[-2 - i + n, -i + n ∈ Integers && n >= 3 + i] *)

Thus, I would consider the result of Sum[1, {j, i, n-3}] acceptable, and the "wrong" result from the explicitly nested Sum[Sum[1, {j, i, n - 3}], {i, n}] to be "user error". However, I am not happy with the result from Sum[1, {i, n}, {j, i, n - 3}], as there is no explicit nesting here. Personally, I would consider this a bug, while realizing that it may not be an easy to fix bug ... Note that in this "nested" sum, i <= n-3 will always be violated.


The workaround is in the spirit of @flinty's answer: we explicitly nest two Sums and manually put conditions on the inner one. I would have hoped that the following works, but unfortunately it does not (the outer sum does not evaluate). Perhaps that makes sense as the ConditionalExpression is not zero when the condition is not satisfied.

Sum[
 Sum[1, {j, i, n - 3}, GenerateConditions -> True],
 {i, n}
]

One possible solution is an explicit Piecewise.

Sum[
 Piecewise[
  {{Sum[1, {j, i, n - 3}], i <= n - 3},
   {0, True}}
  ],
 {i, n}
 ]

enter image description here

Another solution, which seems easier to me, is

Sum[Boole[i <= n - 3], {i, n}, {j, i, n - 3}]

enter image description here

These results are correct.

$\endgroup$
2
$\begingroup$

There is a subtle difference you need to account for with a Piecewise so that it doesn't incorporate the inner sum when your range(i,n-3+1) is empty:

result[n_] := 1 + Sum[
  Piecewise[{{Sum[i + j, {j, i, n - 3}], i < n - 3 + 1}}, 0]
  , {i, 1, n}]

Mathematica can now generate a correct closed form for symbolic $n$ given by result[n]: $$ 1+\left\{ \begin{array}{cc} \frac{1}{2} \left(n^3-7 n^2+16 n-12\right) & n>3 \\ 0 & \text{True} \\ \end{array}\right. $$ This matches up to the results of:

test[n_] := (sum = 1; For[i = 1, i < n + 1, ++i,
   For[j = i, j < n - 3 + 1, ++j,
    sum += i + j;
    ]
   ]; sum)
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.