A general question about summing problems

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

A general question about summing problems

Post by Itachi »

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: 77
Joined: Sat Oct 11, 2008 12:24 pm

Re: A general question about summing problems

Post by DJohn »

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.
User avatar
nicolas.patrois
Posts: 118
Joined: Fri Jul 26, 2013 4:54 pm
Contact:

Re: A general question about summing problems

Post by nicolas.patrois »

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.
Image
v6ph1
Posts: 134
Joined: Mon Aug 25, 2014 7:14 pm

Re: A general question about summing problems

Post by v6ph1 »

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
Image
Post Reply