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
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:
Post a Comment