Tips for Project Euler Problem #78
algorithm, language-agnostic
Solution
Wikipedia can help you here. I assume that the solution you already have is a recursion such as the one in the section "intermediate function". This can be used to find the solution to the Euler problem, but isn't fast.
A much better way is to use the recursion based on the pentagonal number theorem in the next section. The proof of this theorem isn't straight forward, so I don't think the authors of the problem expect that you come up with the theorem by yourself. Rather it is one of the problems, where they expect some literature search.
Problem
This is the problem in question: Problem #78 This is driving me crazy. I've been working on this for a few hours now and I've been able to reduce the complexity of finding the number of ways to stack `n` coins to `O(n/2)`, but even with those improvements and starting from an `n` for which `p(n)` is close to one-million, I still can't reach the answer in under a minute. Not at all, actually. Are there any hints that could help me with this? Keep in mind that I don't want a full solution and there shouldn't be any functional solutions posted here, so as not to spoil the problem for other people. This is why I haven't included any code either.