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?


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.
