Project Euler 543 - Prime-Sum Numbers

Official link: https://projecteuler.net/problem=543

Thought Process

Another really fun problem!

My first idea was to create a matrix such that matrix[n][k] = P(n, k)

1. Clearly matrix[0][k] = 0, matrix[n][0] = 0

2. P(n, 1) = 1 if n is prime, 0 otherwise

3. And P(n, k) = 0 if k > n/2

Now lets say we try to find P(3, 2). Since 2 is the only prime smaller than 3, if there is a sum forming 3 then one of the 2 terms must be 2, hence what were really trying to find is P(3 - 2, 2 - 1) = P(1, 1) = 0.

Similarly if we try to find P(4, 2), then were actually trying to find P(4 - 3, 2 - 1) = P(1, 1) = 0 or P(4 - 2, 2 - 1) = P(2, 1) = 1, therefore P(4, 2) = 1. Like this we can quickly build up any matrix. 

Below I give the S(10) case

1. [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],

2. [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],

3. [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],

4. [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],

5. [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],

6. [0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0],

7. [0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0],

8. [0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0],

9. [0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0], 

10. [0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0],

11. [0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0]]

Which we can see matches the example. From this matrix and further test cases I noticed 3 distinct cases, which are mostly seen to be true due to Goldbach's Conjecture. Take note that π(n) is the prime counting function which I have previously implemented: https://mathslib.readthedocs.io/en/latest/mathslib.html#mathslib.primes.primepi 

Interactive Code

Enter an Integer (yourinput)

Code will output S(yourinput)