Summation of 'for loop' with conditional? I am trying to convert instances of nested 'for' loops into a summation expression. The current code fragment I have is:
for i = 1 to n:
    for j = 1 to n:
        if (i*j >= n):
            for k = 1 to n:
                sum++
        endif

Basically, the 'if' conditional is confusing me. I know that the loops prior will be called n^2 times, but the third loop is only called when $i*j >= n$. How would I write the third summation to account for this, and then evaluate the overall loop's time complexity?
 A: Hint:
The "for" cycle in $k$ is very easy to turn into something simpler...
As for the other parts, see if you can split the problem into easier steps. For example, what happens for $i=1$? And what happens for $i=2$? And $i=3$? And...
A: 
We obtain
  \begin{align*}
\color{blue}{\sum_{i=1}^n}&\color{blue}{\sum_{j=1}^n[i j\geq n]\sum_{k=1}^n1}\tag{1}\\
&=n\sum_{i=1}^n\sum_{j=1}^n[i j\geq n]\\
&=n\left(\sum_{i=1}^n\sum_{{j=\left\lfloor n/i \right\rfloor}\atop{i\mid n}}^n1+\sum_{i=1}^n\sum_{{j=\left\lfloor n/i \right\rfloor+1}\atop{i\not \mid n}}^n1\right)\tag{2}\\
&=n\left(\sum_{i=1}^n\sum_{j=\left\lfloor n/i \right\rfloor+1}^n1+\sum_{{i=1}\atop{i\mid n}}^n1\right)\\
&=n\left(\sum_{i=1}^n\left(n-\left\lfloor\frac{n}{i}\right\rfloor\right)+\tau(n)\right)\tag{3}\\
&=n\left(n^2-\sum_{i=1}^n\left\lfloor\frac{n}{i}\right\rfloor+\tau(n)\right)\\
&\,\,\color{blue}{=n\left(n^2-\sum_{i=1}^{n-1}\tau(i)\right)}\tag{4}\\
&\,\,\color{blue}{\sim n^3-n^2\left(\log n+2\gamma-1\right)+O\left(n^{3/2}\right)}\tag{5}
\end{align*}

Comment:


*

*In (1) we use Iverson brackets to represent the condition $ij\geq n$.

*In (2) we rewrite the expression using the floor function. Note the  $\pm 1$ technicality regarding the range of summation.

*In (3) we simplify the inner sum of the left-hand term and use the $\tau$-function which counts the number of divisors.

*In (4) we use an identity stated in A006218 to get rid of the floor function.

*In (5) we use an asymptotic expansion which is also stated in OEIS/A006218.
A: At the basic level, for loops are also rewritable as conditionals. Anyways, on to the meat of the problem. The conditional can be removed if you replace 1 in the previous loop with ceil(n/i). So it can be rewritten as:
for i = 1 to n: 
     for j = ceil(n/i) to n:
             for k = 1 to n:
                sum++
Then the inner 2 loops compress to:
sum+=n*(n-ceil(n/i)+1)
Which then gets called n times, but the sum can be wriiten as:
$$n\sum_{i=1}^{n}(n-\lceil\frac{n}{i}\rceil+1)$$
As to the time complexity of the code as wriiten...,  it'll take, okay I don't quite know that part. 
