## A general question about summing problems

Primes, divisors, arithmetic, number properties, ...
Itachi
Posts: 1
Joined: Mon Aug 03, 2015 7:46 am

### A general question about summing problems

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?

DJohn
Posts: 42
Joined: Sat Oct 11, 2008 11:24 am

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

v6ph1
Posts: 113
Joined: Mon Aug 25, 2014 6:14 pm

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