Hacker News Reader

Comment by ttsiodras | Hacker News Reader

Wow - speechless :-)

The correlation with my program's results is clear (the coefficients are my last column) - any references as to why?

The power series for 1/(1-x^n) is 1 + x^n + x^2n + x^3n + ... in which the term x^i is the number of ways of forming i as a sum of zero or more n.

Multiplying two power series maintains that property -- the x^j term in the product of two power series comes from x^i in one power series and x^(j-i) in the other power series, just like a sum of j pence made out of two types of coins has to be i pence worth of one type of coin and j-i pence worth of the other type of coin.

Converting (1/(1-x)) * (1/(1-x^2)) * ... into 1/((1-x) * (1-x^2) * ...) is just routine algebraic manipulation, which I claim without proof is valid for power series.

This is why you should treat Project Euler more as a way to learn mathematics and less as a way to practice code. Most of their problems can, and IMO should, be solved by pen and paper alone.

To be fair, I wouldn't want to compute the 200th term of a power series by hand. I could do it, but it would probably take me several attempts to do that much arithmetic without making a mistake somewhere along the way.

(sorry to necrobump!)

That's a fair point. I should revisit my critique: IMO, PE should be used to practice conceptual mathematics; if you're trying to perform an exhaustive search, for example, you might want to see if there's a better way.

That's because the series is the generating function for the number of ways to make 2 pounds with those coins.

Reply on news.ycombinator.com