3 ms·
Alternatively, you can ask Wolfram Alpha to compute a power series: http://www.wolframalpha.com/input/?i=series+1%2F%28%281-x%29*%281-x%5E2%29*%281-x%5E5%29*%28
by cperciva 15y ago
Alternatively, you can ask Wolfram Alpha to compute a power series:
http://www.wolframalpha.com/input/?i=series+1%2F%28%281-x%29*%281-x%5E2%29*%281-x%5E5%29*%281-x%5E10%29*%281-x%5E20%29*%281-x%5E50%29*%281-x%5E100%29*%281-x%5E200%29%29+at+x%3D0+to+order+200 http://www.wolframalpha.com/input/?i=series+1%2F%28%281-x%29...
- ttsiodras 15y agoWow - speechless :-) The correlation with my program's results is clear (the coefficients are my last column) - any references as to why?
- cperciva 15y agoThe 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.
- owenmarshall 15y agoThis 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.
- cperciva 15y agoTo 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.
- owenmarshall 15y ago(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.
- pmiller2 15y agoThat's because the series is the generating function for the number of ways to make 2 pounds with those coins.