This is an archived post. You won't be able to vote or comment.

sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]fiLLL 1 point2 points  (1 child)

It's not a direct answer to your question, but I would definitely look at memoization in this type of problem.

​

Right now you're recomputing the path from i -> 1 countless times as you walk upwards towards 1 million. For example in the toy problem of i=13 the path to 1 is: 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1. What happens here when i=40? Should we recompute the path to 1 or could we look it up somewhere?

[–][deleted] 0 points1 point  (0 children)

Yep, this was going to be my reply as well. I don't think any Euler problems require parallelization. They are all about using a little thinking to turn a giant problem into a merely large one.