1

I'm doing the Project Euler problem 78

Let p(n) represent the number of different ways in which n coins can be separated into piles. For example, five coins can be separated into piles in exactly seven different ways, so p(5)=7

Find the least value of n for which p(n) is divisible by one million.

I'm trying to solve this problem using recursion. I know is not the optimal solution neither the fastest one, but I want to make this work if possible. Around n = 6000 it gives me:

MemoryError: Stack overflow

And that is not the only problem. I checked online and the solution is around 53,000. My matrix goes only to 10,000x10,000. If i go to 60,000x60,000 it return a MemoryError. Here is my code:

import sys
from time import process_time as timeit

sys.setrecursionlimit(100000)

table = [10000 * [0] for i in range(10000)]

def partition(sum, largestNumber):
    if (largestNumber == 0):
        return 0

    if (sum == 0):
        return 1

    if (sum < 0):
        return 0

    if (table[sum][largestNumber] != 0):
        return table[sum][largestNumber]

    table[sum][largestNumber] = partition(sum,largestNumber-1) + partition(sum-largestNumber,largestNumber)
    return table[sum][largestNumber]



def main():
    result = 0
    sum = 0
    largestNumber = 0
    while (result == 0 or result%100000 != 0):
        sum += 1
        largestNumber += 1
        result = int(partition(sum,largestNumber))
        if sum%1000 == 0:
            print('{} {}'.format(sum,timeit()))

    print("n = {}, resultado = {}".format(sum,result))
    print('Tempo = {}'.format(timeit()))
if __name__ == '__main__':
    main()
Community
  • 1
  • 1
João Vitor Degrandi
  • 3,417
  • 2
  • 8
  • 8
  • Consider using [`sqlite3`](https://docs.python.org/3/library/sqlite3.html)? It automatically spills over to disk when the data gets too large for main memory. – B. Shefter Mar 18 '19 at 21:03
  • 1
    Also, [`sys.getrecursionlimit()`](https://docs.python.org/3/library/sys.html#sys.getrecursionlimit) tells you the maximum depth of the Python interpreter stack. – B. Shefter Mar 18 '19 at 21:08
  • @B.Shefter, i know. But at `100,000` recursion i shouldn't have a problem to reach `50,000` – João Vitor Degrandi Mar 18 '19 at 22:00
  • You don't have enough call-stack space to do this. Use an iterative solution. See this: https://stackoverflow.com/questions/26873627/why-does-python-have-a-maximum-recursion-depth – juanpa.arrivillaga Mar 19 '19 at 08:05

0 Answers0