Project Euler 78 - Coin Partitions
Project Euler 78 - Coin Partitions
Official link: https://projecteuler.net/problem=78
Thought Process
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 https://en.wikipedia.org/wiki/Partition_(number_theory) I found the Pentagonal Number Theorem.
All we need to do is implement this function in python, not very tricky.
Make sure to account for the sign (+1, -1)
Make sure to add both k = a, - a
Remember to that if a = n-g(k) < 0 then p[a] = 0
Interactive Code
Interactive Code
No interactive code for this problem, my code is given below