Python MemoryError occurring with large loop

Question

I'm trying to create a script to solve a question for me on Project Euler, but it keeps returning a MemoryError. I have absolutely no idea why.

divisible = True
possible = dict()

for i in xrange(1, 100000000):
    for n in xrange(1, 21):
        if i%n != 0:
            divisible = False
        else:
            if i in possible:
                possible[i].append(n)
            else:
                possible[i] = [n]

        if len(possible[i]) == 20:
            print i
            break

Python seems to think it occurs on this line possible[i] = [n]

Answer 1

The problem is in your line

if len(possible[i]) == 20:

You mean to say

if len(possible) == 20:

As it is, your code will keep on running - and presumably, since the the loop count is so large, some stack fills up...

Also - although I don't know for sure what you are trying to achieve, your break command is in the innermost loop - so you break out of it, then go around again... and since the length will only be exactly 20 once, you are still stuck. Check your logic.

for example, the following small change to your code produces useful output (although I don't know if it's useful for you... but it might give you some ideas):

divisible = True
possible = dict()

for i in xrange(1, 100000000):
    for n in xrange(1, 21):
        if i%n != 0:
            divisible = False
        else:
            if i in possible:
                possible[i].append(n)
            else:
                possible[i] = [n]

    if len(possible) == 20:
        print i
        break
    else:
        print i, possible[i]

Output:

1 [1]
2 [1, 2]
3 [1, 3]
4 [1, 2, 4]
5 [1, 5]
6 [1, 2, 3, 6]
7 [1, 7]
8 [1, 2, 4, 8]
9 [1, 3, 9]
10 [1, 2, 5, 10]
11 [1, 11]
12 [1, 2, 3, 4, 6, 12]
13 [1, 13]
14 [1, 2, 7, 14]
15 [1, 3, 5, 15]
16 [1, 2, 4, 8, 16]
17 [1, 17]
18 [1, 2, 3, 6, 9, 18]
19 [1, 19]
20

EDIT reading through the code more carefully, I think what you are trying to do is find the number that has exactly 20 factors; thus your condition was correct. The problem is that you are storing all the other terms as well - and that is a very very large number of lists. If you are only after this last number (after all the only output is i just before the break), then you really don't need to keep all the other terms. The following code does just that - it's been running merrily on my computer, taking about 20 MB of memory for the longest time now (but no answer yet...)

divisible = True
possible = [];
biggest = 0;
bigN = 100000000;

for i in xrange(1, bigN):
    for n in xrange(1, 21):
        if i%n != 0:
            divisible = False
        else:
            if len(possible) > 0:
                possible.append(n)
            else:
                possible = [n]

    if len(possible) >= 20:
        print i
        print possible
        break
    else:
        if bigN < 1000:
            print i, possible; # handy for debugging
        if biggest < len(possible):
            biggest = len(possible);
        possible = []

The "manual" way to calculate what you are doing is finding the prime factors for all numbers from 1 to 20; counting the largest number of times a prime occurs in each; and taking their product:

2  = 2
3  =     3
4  = 22
5  =        5
6  = 2   3
7  =          7
8  = 222
9  =     33
10 = 2      5
11 =              11
12 = 22  3
13 =                 13
14 = 2         7
15 =     3  5
16 = 2222
17 =                    17
18 = 2   33
19 =                      19
20 = 22     5

Answer: (2*2*2*2)*(3*3)*5*7*11*13*17*19 = 232792560

Answer 2

I would say you need to change the approach here. You need solutions which fit under the 1 minute rule. And discussing the solution here defeats the very purpose of Project Euler. So I would suggest that you think of a different approach to solve the problem. An approach which might solve the problem in less than a second.

As for the memory issue, with the current approach, it is almost impossible to get rid of it. So changing the approach will solve this issue too. Though this post does not answer your question, it is in line with Project Euler's principles!

Answer 3

The check should be outside the innerloop for it to terminate properly. Otherwise, the program would never stop, at intended exit.

divisible = True
possible = dict()

for i in xrange(1, 100000000):
    for n in xrange(1, 21):
        if i%n != 0:
            divisible = False
        else:
            if i in possible:
                possible[i].append(n)
            else:
                possible[i] = [n]
    if len(possible[i]) == 20:
        print i
        break

BTW, a faster method would be to find LCM than going for a bruteforce method like this.

edit: One variant which uses no memory.

divisible = True
possible = []
for i in xrange(0, 1000000000):

    count = 0
    for n in xrange(1, 21):
        if i%n != 0:
            divisible = False
        else:
            count += 1
    if count == 20:
        possible.append(i)
        print i
    else:
        print "\r", "%09d %d %d" % (i, 232792560, count),

print possible

Answer 4

A quick back of the envelope calculation. You have something like 100000000 integers which if you stored them all would be something on the order of 0.4 Gb (in C). Of course, these are python integers, so each one is more than 4 bytes ... On my system, each is 24(!) bytes which takes your 0.4 Gb up to 2.34 Gb. Now you have each one stored in up to 21 lists ... So that's (up to) an additional 21 pointers to each. Assuming a 4byte pointer to an int, you can see that we're already starting to consume HUGE amounts of memory.

Also note that for performance reasons, lists are over-allocated. It's likely that you're using way more memory than you need because your lists aren't full.

Of course, you're not actually storing them all, and you have an early break condition which (apparently) isn't getting hit. It's likely that you have a logic error in there somewhere.

Answer 5

The memory error is occuring due to the size of :

possible = dict()

One you keep pushing integers into it, its size keeps on growing, and you get memory error. Carefully see if that can be avoided in the solution.eg. If the answer requires only to tell the count of factors, and not all factors, then do not store all values in a list and calculate its length. Instead increment counters for each number. I am not sure what the question is, but this can be replaced by this :

if len(possible[i]) == 20:
            print i
            break

can be :

if i in possible:
            possible[i] += 1
        else:
            possible[i] = 0   
if possible[i] == 20:
                print i
                break