Project Euler 78 - Coin Partitions

Official link:

Thought Process

After I solved Problem 76, and 77, this problem made me realise that my code was in-efficient. I could solve the problem with my previous code in ~ 500 seconds, which is much too long as after some research on I found the Pentagonal Number Theorem.

All we need to do is implement this function in python, not very tricky.

  1. Make sure to account for the sign (+1, -1)

  2. Make sure to add both k = a, - a

  3. Remember to that if a = n-g(k) < 0 then p[a] = 0

Interactive Code

No interactive code for this problem, my code is given below