Simplifying Summation from loop with an if statmen

问题:

I'm having trouble figuring out how to simplify this code to summations since it has an if statement in it.

sum=0
for (i = 1 to n ){
    for (j = 1 to i^2){
        if (j % i ==0) then
            for (k = 1 to j){
                sum++
            }
        }
    }
}

I know the if statement will execute i times every loop.

1%1 = 0
2%2 = 0
4%2 = 0
3%3 = 0
6%3 = 0
9%3 = 0

and so on.

This is what I have so far (see link below), forgive the i^2 notation, I can't post images yet without rep. Again, the inner summation is i^2 not 2 choose i.

http://www.HostMath.com/Show.aspx?Code=%5Csum%5Climits_%7Bi%3D1%7D%5En%5Csum%5Climits_%7Bj%3D1%7D%5Ei%5E%7B2%7D%20%5Csum%5Climits_%7Bk%3D1%7D%5Ej%0A(1)

I want to simplify the inner summation to j, but it only happens, i times. I feel like this is very simple and I am not seeing the obvious connection.

回答1:

That is my proposed solution:

sum=0
for (i = 1 to n )
{
  for (j = i to i^2, step=i){
    sum = sum + j
  }
}

UPDATE It looks like square pyramidal number, so you can just write:

sum = (2*n^3 + 3*n^2 + n / 6)

回答2:

for (k = 1 to j) {
    sum++
}

Note that the for-loop above increments sum j times, which is equivalent to the following line:

sum = sum + j

Note that the condition if (j % i ==0) evaluates to true when j is a multiple of i, so you can actually change your for-loop indexed by j to be incremented by i instead of 1 after each iteration. So you can have the following equivalent code instead:

sum = 0
for (i = 1; i <= n; i++) {
    for (j = 0; j <= i^2; j = j + i) {
        sum = sum + j
    }
}

Note: For simplicity, I have changed the starting index of j to 0 instead of 1. If we start from 1, j will take values 1 + i, 1 + 2i, ... instead of the multiples of i.

回答3:

Fast solution:

  int sum = n * (n + 1) / 2;
  sum *= sum;
  sum += n * (n + 1) * (2 * n + 1) / 6;
  sum /= 2;

What code is doing:

  int sum = 0, i, j;
  for(i = 1; i <= n; i++)
    for(j = 1; j <= i; j++)
        sum += i * j;

回答4:

I think the approach that is closest to what you have but doesn't have an if is the following.

sum = 0
for (i = 1 to n)
  for (j = 1 to i)
    for (k = 1 to i*j)
      sum++

Basically, you change j so that instead of looping over everything from 1 to i^2 and then skipping anything that isn't a multiple of i, you just have j loop over the multiples.

As has been stated in other answers, there are far more efficient expressions for this sum that do not require any loops.

回答5:

The answer that I marked as correct was wrong. This was the answer that was given to me. I will do my best to say it properly.

The sum from i = 1 to n, of the sum from j = 1 to i squared for even j is equal approximately to the sum from i = 1 to n of i squared times i squared plus one all over 2.

(or the last part again) is equal to approximately:

the sum from i =1 to n of (i^2 * [(i^2) + 1]) / 2 which is Theta n^5.

THIS is the correct answer