Problem 292

[sivakd]

Hi, I finally have a solution that is valid for P(30) and P(60). The problem now is that it is very slow (crossing 1 minute limit for P(80). Before I embark on further optimization or a different strategy, I am curious on what is the typical runtime people submitted? I am sure there has to be one solution that takes less than 18 minutes 44 seconds .

[harryh]

The fastest solutions are 0.1 sec to a few seconds. There are many solutions approx. 12 sec - 50 sec and a few that run for considerably more than 1 min.

[sivakd]

Thanks harry. With memoization the time reduces to 1.5 seconds but the answer is wrong . I don't know what to make of it because P(30) and P(60) are still correct. May be this is one of those problems where with larger n, the algorithm has some bugs? I need to figure that out.

[sivakd]

Ok, finally done. Still 1.5 seconds. I had one premature optimization that's throwing the value off for higher n. I removed it and got the right answer. It would be very hard to figure out what was wrong with that optimization. I won't sweat on it though.

[stijn263]

p(120) is larger than 2³¹ so you might have an overflow problem?

Good luck!

edit: I see you already got it. Good job!

[sivakd]

Thanks stijn263. I couldn't resist to figure out what the issue was. It is not related to overflow. It turned out that the primitive pythagorean triplets don't get generated in increasing order of hypotenuse. Just a bad assumption. So the issue actually kicked in for P(83). Hopefully I am not giving away too much info.

[PurplePuppy]

My solution to problem 292 runs too slowly!
My 6-layer nest of for loops have already caused it to take around 3 minutes for P(60). Maybe I should learn some memoization. Do the solutions of everyone make use of memoization for this problem?