Summation of 'for loop' with conditional?

Question

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?

Answer 1

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...

Answer 2

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.

Answer 3

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.