project euler problem 076

Counting summations

Project Euler problems become interesting from 60--70. The first 50 problems are mainly warm-up problems. Now, we can see  some interesting math problems such as Pell equations and partition.  

This problem is interesting but still simple. It is very similar to problem 31 and can be solved recursively or with generating function.

update: 09/25/2017: The simplest way of solving this problem is using dynamic programming, this is a  knapsack problem. 
The answer for N = 10000 can be found in 0.74 second.