# A puzzle related to loops.

For a given input $N$, how many times does the enclosed statement executes?

for $i$ in $1\ldots N$ loop
$\quad$for $j$ in $1\ldots i$ loop
$\quad$$\quadfor k in j\ldots i loop \quad$$\quad$$\quad$$sum = sum + i$ ;
\quad$$\quadend loop; \quadend loop; end loop; Can anyone figure out an easy way or a formula to do this in general. - Should the 'for k in i..j loop' have the i and j reversed? – copper.hat Nov 29 '12 at 8:35 I've retagged your question since it is definitely not about linear-programming, see the tag-wiki. Of course, if you can find other appropriate tags, feel free to add them or replace the ones I've put to your post. – Martin Sleziak Nov 29 '12 at 8:52 @copper.hat no.. it's just the way it is :) – Vishnu Vivek Nov 29 '12 at 11:28 @MartinSleziak Thanks Martin!! – Vishnu Vivek Nov 29 '12 at 11:28 ## 4 Answers The number of times the inside statement is executed is S = \sum_{i=1}^N \sum_{j=1}^i \sum_{k=i}^j 1. \begin{eqnarray} S &=& \sum_{i=1}^N \sum_{j=1}^i (i-j+1) \\ & = & \sum_{i=1}^N (i(i+1)-\frac{1}{2} i(i+1)) \\ & = & \frac{1}{2} \sum_{i=1}^N (i^2 +i) \\ & = & \frac{1}{2} (\frac{1}{6}N(N+1)(2N+1)+ \frac{1}{2}N (N+1)) \\ & = & \frac{1}{6} N(N+1)(N+2) \end{eqnarray} - Since he is not adding 1 but i in the innermost cycle, the number of executions is not the same as the sum. – Martin Sleziak Nov 29 '12 at 8:48 That is correct. I am computing the number of times the statement is executed, not the sum? – copper.hat Nov 29 '12 at 8:49 My mistake, I should have read the OP more carefully. (I assumed he wants the sum.) – Martin Sleziak Nov 29 '12 at 8:50 Initially I did too. – copper.hat Nov 29 '12 at 8:51 @copper.hat Thank you very much!! this is the best I've got by far.. – Vishnu Vivek Nov 29 '12 at 11:32 So you're asking for the value of$$ S = \sum_{i=1}^N\sum_{j=1}^i(i-j+1). $$Write S_i for the inner sum. Then$$ S_i = i^2 - \sum_{j=1}^i j + i = i^2 - \frac{i(i+1)}2 + i = \frac12 i^2 + \frac12 i.Then the outer sum is \begin{align*} S &= \frac12\sum_{i=1}^N i^2 + \frac12\sum_{i=1}^n i\\ &= \frac{N(N+1)(2N+1)}{12} + \frac{N(N+1)}4\\ &= \frac{N(N+1)(N+2)}{6}. \end{align*} - Thank you very much!! – Vishnu Vivek Nov 29 '12 at 11:34 For any value of i, the j-loop executes i times. For any value of j, the k-loop executes i-j+1 times, and each time we add i to the sum. Assuming the initial sum was 0, we have:\begin{align*}sum&=\sum_{i=1}^N \sum_{j=1}^i i(i-j+1)=\sum_{i=1}^N \sum_{j=1}^i (i^2+i-ji)=\sum_{i=1}^N \left((i^2+i)i-i\frac{i(i+1)}{2}\right)=\\ &=\frac12\sum_{i=1}^N \left(2i^3+2i^2-i^3-i^2\right)=\frac12\sum_{i=1}^N\left(i^3-i^2\right)=\frac12\left(\frac{N^2(N+1)^2}{4}-\frac{N(N+1)(2N+1)}{6}\right)=\\ &=\frac{1}{24} (N-1) N (N+1) (3 N+2)\end{align*}$$- @VISHNU VIVEK: I thought you wanted the sum, but reading your question again, I see that you just wanted the number of times the loop executes. In that case, the other answers are the correct. I left my answer anyway, just in case :) – Dennis Gulko Nov 29 '12 at 9:02 I wanted the no of times of execution of that statement.. but thanks anyways Dennis – Vishnu Vivek Nov 29 '12 at 11:34 There is also a combinatorical way to find the solutiopn of you question. Check wich values takes the tupel (j,k,i) in the most inner loop? Each tuple (j,k,i) with 1 \le k \le N exactly once. So • each tuple (j,k,i) with 1 \le j<k<i \le N • each tuple (j,j,i) with 1 \le j<i \le N • each tuple (j,i,i) with 1 \le j<i \le N • each tuple (j,j) with 1 \le j \le N The first number is \binom{N}{3}, the second and the third is \binom{N}{2}, the fourth is \binom{N}{1}.$$(\binom{N}{3} + \binom{N}{2} ) + (\binom{N}{2}+ \binom{N}{1})=\binom{N+1}{3}+\binom{N+1}{2}=\binom{N+2}{3}=\frac{n(n+1)(n+2)}{6}=\binom{n+2}{3}$Edit This result can be proved in a direct way: Take the$n+2$element set$M=\{\text{"j=k"},1,...,N,\text{"i=k"}\}$. The set contains of the$N$numbers$1,...,N$and the two strings$\text{"j=k"}$and$\text{"i=k"}$. A three element subset$S$of$M$can be of exactly one of the following types: 1.$S=\{j,k,i\} , 1 \le j \lt k \lt i \le N$2.$S=\{\text{"j=k"},k,i\}, 1 \le k \lt i \le N$3.$S=\{j,k,\text{"i=k"}\}, 1 \le j \lt k \le N$4.$S=\{\text{"j=k"},k,\text{"i=k"}, 1 \le k \le N$The sets of these four list items correspond to the tuples of the corresponding items of the former list. But this four types of sets contain all the three element subsets of the set M and the number of three element subsets of$M$is$\binom{n+2}{3}\$.

-
thank you for the answer!!! – Vishnu Vivek Nov 30 '12 at 12:01
added a simpler way to get the result – miracle173 Dec 2 '12 at 7:50