CODEWITHSUNDEEP
pythonloopsfor-loop
AlexBrand
AlexBrand

Reputation: 12401

Python - Sum of numbers

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

Upvotes: 3

Views: 7417

Answers (3)

Jim Sjoo
Jim Sjoo

Reputation: 326

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)]

Upvotes: 0

aaronasterling
aaronasterling

Reputation: 70984

[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]

Upvotes: 2

Alex Martelli
Alex Martelli

Reputation: 881497

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.

Upvotes: 1

Related Questions