Problem 391

[ffff0]

I think there is no pattern, since limit is so low (1000).
Running program now which calculate it value individually.

[Larry_Hignight]

Hello all,

This is my first post, and boy am I stuck on this problem. =)

What I have done so far:

• I understand the problem.
• I can calculate the final value in Sk for any M(n).
• I can correctly solve the Σ(M(n))3 = 8150 example in about 20 seconds of CPU time with an O(n) algorithm.
• I also realize this approach won't succeed because the problem space is increasing exponentially.

Unfortunately, I can't think of anything else to cope with a problem space of this size and was wondering if someone might be able to point me to another problem that might nudge me in the right direction.

[Marcus_Andrews]

For many of the tougher Project Euler challenges, being able to synthesize the example-case solutions is a good sign that you've got a fairly good chunk of the puzzle figured out already. What I am about to say might sound obvious, but it might help to do some additional analysis of the problem. Play around with what you've got and see if there is some pattern or structure you can take advantage of to help speed up your algorithm.

[ffff0]

As I noted relatively low upper limit suggest that each value must be obtained individually and that computing and/or memory requirements are beyond O(n).

My approach works in O(n^4) time and takes O(n^3) memory, but it wasn't the best one.