Memory limit exceeded in Python

Question

I am solving a problem that needs either a list of integers or a dictionary of size 10^18. Upon running the code the compiler throws an error message saying "Memory Limit Exceeded".

Here is my code:

def fun(l, r, p):
    #f = [None, 1, 1]
    f = {0:0, 1:1, 2:1}
    su = 0
    for i in range(1, r):
        if i%2 == 0:
            f[i+2] = 2*f[i+1] - f[i] + 2
            #f.append(2*f[i+1] - f[i] + 2)
        else:
            f[i+2] = 3*f[i]
            #f.append(3*f[i])

    for k in range(l, r):
        su = su + f[k]

    su = (su + f[r]) % p
    print(su)

t, p = input().split()
p = int(p)
t = int(t)
#t = 3
#p = 100000007
for i in range(t):
    l , r = input().split()
    l = int(l)
    r = int(r)
    fun(l, r, p)

It is showing memory limit exceeded with a maximum memory usage of 306612 KiB.

Answer 1

Two observations here:

• You don't need to store all numbers simultaneously. You can use the deque and generator functions to generate the numbers by keeping track of only the last three digits generated instead of the entire sequence.

    import itertools
    from collections import deque
  
    def infinite_fun_generator():
        seed = [0, 1, 1]
        dq = deque(maxlen=2)
        dq.extend(seed)
        yield from seed
        for i in itertools.count(1):
            if i % 2 == 0:
                dq.append(2 * dq[-1] - dq[-2] + 2)
            else:
                dq.append(3 * dq[-2])
            yield dq[-1]
  
    def fun(l, r, p):
        funs = itertools.islice(infinite_fun_generator(), l, r + 1)
        summed_funs = itertools.accumulate(funs, lambda a, b: (a + b) % p)
        return deque(summed_funs, maxlen=1)[-1]
  

• You might have a better chance asking this in Math.SE since I don't want to do the math right now, but just like with the Fibonacci sequence there's likely an analytic solution that you can use to compute the nth member of the sequence analytically without having to iteratively compute the intermediate numbers and it may even be possible to analytically derive a formula to compute the sums in constant time.