Python - Sum of numbers

Question

I am trying to sum all the numbers up to a range, with all the numbers up to the same range.

I am using python:

limit = 10
sums = []
for x in range(1,limit+1):
    for y in range(1,limit+1):
        sums.append(x+y)

This works just fine, however, because of the nested loops, if the limit is too big it will take a lot of time to compute the sums.

Is there any way of doing this without a nested loop?

(This is just a simplification of something that I need to do to solve a ProjectEuler problem. It involves obtaining the sum of all abundant numbers.)

Answer 1

[x + y for x in xrange(limit + 1) for y in xrange(x + 1)]

This still performs just as many calculations but will do it about twice as fast as a for loop.

from itertools import combinations

(a + b for a, b in combinations(xrange(n + 1, 2)))

This avoids a lot of duplicate sums. I don't know if you want to keep track of those or not.

If you just want every sum with no representation of how you got it then xrange(2*n + 2) gives you what you want with no duplicates or looping at all.

In response to question:

 [x + y for x in set set1 for y in set2]

Answer 2

If a for comprehension isn't to your liking you can take a look at itertools and use:

map( sum, product( range( limit + 1 ), repeat=2 ) )

Here is the description of product, taken right from the online doc:

Equivalent to nested for-loops in a generator expression. For example, product(A, B) returns the same as ((x,y) for x in A for y in B).

The nested loops cycle like an odometer with the rightmost element advancing on every iteration. This pattern creates a lexicographic ordering so that if the input’s iterables are sorted, the product tuples are emitted in sorted order.

To compute the product of an iterable with itself, specify the number of repetitions with the optional repeat keyword argument. For example, product(A, repeat=4) means the same as product(A, A, A, A).

So that the function returns a list of the sums of two entries from the combinatorial product of range( limit + 1 ). You could substitute whatever you'd like in place of range( limit + 1), even supplying your own list/tuple/set of entries.

Answer 3

I am trying to sum all the numbers up to a range, with all the numbers up to the same range.

So you want to compute limit**2 sums.

because of the nested loops, if the limit is too big it will take a lot of time to compute the sums.

Wrong: it's not "because of the nested loops" -- it's because you're computing a quadratic number of sums, and therefore doing a quadratic amount of work.

Is there any way of doing this without a nested loop?

You can mask the nesting, as in @aaron's answer, and you can halve the number of sums you compute due to the problem's simmetry (though that doesn't do the same thing as your code), but, to prepare a list with a quadratic number of items, there's absolutely no way to avoid doing a quadratic amount of work.

However, for your stated purpose

obtaining the sum of all abundant numbers.

you're need an infinite amount of work, since there's an infinity of abundant numbers;-).

I think you have in mind problem 23, which is actually very different: it asks for the sum of all numbers that cannot be expressed as the sum of two abundant numbers. How the summation you're asking about would help you move closer to that solution really escapes me.

Answer 4

I'm not sure if there is a good way not using nested loops.

If I put on your shoes, I'll write as following:

[x+y for x in range(1,limit+1) for y in range(1,limit+1)]