Hello. From what Iv'e seen, many problems require large summations.

Since it's Computer Science, I'd assume that we are required to find ways to make the problem easier, and not sum a lot of numbers so Iv'e been trying to find mathematical properties that make it easier to sum. However, if I do need to simply write a program that'd sum it, I'd never find a solution. So, for my question:

Am I supposed to write a program that'd sum about 1000 integers?

If not, what are some neat tricks to make summation easier?

## A general question about summing problems

### Re: A general question about summing problems

Let's say you wanted to add the first 10 odd numbers: 1 + 3 + 5 + 7 + 9 + 11 + 13 + 15 + 17 + 19. We'll start by saying

S = 1 + 3 + 5 + 7 + 9 + 11 + 13 + 15 + 17 + 19.

Now comes the trick. We can rearrange the numbers

S = 19 + 17 + 15 + 13 + 11 + 9 + 7 + 5 + 3 + 1

and add these two expressions

2S = (1+19) + (3+17) + ... + (19+1)

On the right, we have 10 lots of 20. So 2S = 200, or S = 100.

The idea is to assign the sum to a variable, then manipulate the expression in some way that gives a simple equation we can solve. In this case, the manipulation involved pairing numbers so each pair gave the same sum, and we could replace lots of additions with a single multiplication.

Another example: you want to sum a geometric series, where each term is a constant multiple of the previous one. For example, adding powers of two, so each term is double the last. We start again by assigning the sum to S:

S = 1 + 2 + 4 + 8 + ... + 512 + 1024.

Now if we double this equation, we get

2S = 2 + 4 + 8 + ... + 1024 + 2048

Subtract the first from the second, and most of the series cancels, leaving 2S - S = -1 + 2048, or S = 2047.

Arithmetic and geometric series like these appear often enough that it's worth remembering the general solutions.

S = 1 + 3 + 5 + 7 + 9 + 11 + 13 + 15 + 17 + 19.

Now comes the trick. We can rearrange the numbers

S = 19 + 17 + 15 + 13 + 11 + 9 + 7 + 5 + 3 + 1

and add these two expressions

2S = (1+19) + (3+17) + ... + (19+1)

On the right, we have 10 lots of 20. So 2S = 200, or S = 100.

The idea is to assign the sum to a variable, then manipulate the expression in some way that gives a simple equation we can solve. In this case, the manipulation involved pairing numbers so each pair gave the same sum, and we could replace lots of additions with a single multiplication.

Another example: you want to sum a geometric series, where each term is a constant multiple of the previous one. For example, adding powers of two, so each term is double the last. We start again by assigning the sum to S:

S = 1 + 2 + 4 + 8 + ... + 512 + 1024.

Now if we double this equation, we get

2S = 2 + 4 + 8 + ... + 1024 + 2048

Subtract the first from the second, and most of the series cancels, leaving 2S - S = -1 + 2048, or S = 2047.

Arithmetic and geometric series like these appear often enough that it's worth remembering the general solutions.

- nicolas.patrois
**Posts:**117**Joined:**Fri Jul 26, 2013 3:54 pm-
**Contact:**

### Re: A general question about summing problems

Other tricks:

* When the sum is double (or multiple), try to exchange symbols.

* Try to use the Chinese remainder theorem to split the sum in parts.

* When the sum is double (or multiple), try to exchange symbols.

* Try to use the Chinese remainder theorem to split the sum in parts.

### Re: A general question about summing problems

Or sometimes you have problems, for which the intermediate solutions of the highest summand are solutions for the other summands.

E.g. Sum 3^(2^x) = 3 + 9 + 81 + ...

Using Square and Multiply, you get 3 and 9 while you calc 81.

(In many of these cases, your base will be a matrix)

Some problems have a modulus after the sum - you than may find a cycle *1:

Sum(x=0..10) 2^x % 7 = 1 + 2 + 4 + 1 + 2 + 4 + 1 + 2 + 4 + 1 + 2 = 3*(1+2+4) + 1+2

*1 The cycle may not include some of the first elements

E.g. Sum 3^(2^x) = 3 + 9 + 81 + ...

Using Square and Multiply, you get 3 and 9 while you calc 81.

(In many of these cases, your base will be a matrix)

Some problems have a modulus after the sum - you than may find a cycle *1:

Sum(x=0..10) 2^x % 7 = 1 + 2 + 4 + 1 + 2 + 4 + 1 + 2 + 4 + 1 + 2 = 3*(1+2+4) + 1+2

*1 The cycle may not include some of the first elements