[Solved] Memory + dynamic programming or recursion

by


You do not need anywhere near that many entries (10^9 / 3). Note that you need only the values mod 10^6. You have a recurrence relationship among these:

a[n] = a[n-1]^2 + 2

Each value depends only on the previous one, so there will be a simple sequence of numbers. The relation will have a period of no more than 10^6. Since they’re all odd, the maximum length is cut in half.

As it turns out, the sequence repeats after 5003 terms, with a period of 5000: 3, 11, 123 do not appear later in the sequence.

So, forget that huge array. Compute the 5003 terms you need. Now for any input number N, you have 3 cases:

(1) N is not divisible by 3: return 0
else N is divisible by 3; call the quotient M
(2) M <= 3: return arr[M]
(3) else, get the needed subscript as m = ((M-3) mod 5000) + 3;
       return arr[m]

You can now handle arbitrarily large input.

solved Memory + dynamic programming or recursion