Tuesday, June 10, 2014

Project Euler

I spent a lot of time being frustrated with Problem 472 . It seems like a problem that should admit to a nice closed form solution but solving it ended up being a (fun) pattern matching exercise.

The main thing to realize is that you are asked to sum the function $f$ over $10^{12}$ terms, but there is really no way to do that in under 1 minute of execution time. (Of course, I did not realize this until I had spent a great deal of time devising efficient algorithms for evaluating $f$ at a single value.)
You have to group the terms and add over the groups. One way yields about $\log N$ terms, which
brings the execution time down to < 0.1s.

It's all about pattern matching -- I guess....hacking + math = project euler

No comments: