Wednesday, September 9, 2015

Project Euler: Integral median

From Project Euler:

ABC is an integral sided triangle with sides a≤b≤c.
mc is the median connecting C and the midpoint of AB. 
F(n) is the number of such triangles with c≤n for which mc has integral length as well.
F(10)=3 and F(50)=165.

Find F(100000).


Let d be the median.  Then d can be calculated by (1):

d = sqrt(2 * a^2 + 2 * b^2 - c^2) / 2


A brute-force solution is to loop through the range of a, b, and c. There are some conditions / optimization to reduce the scope and improve performance:
  • a, b, c can form a proper triangle (triangle inequality. i.e. sum of any two sides is bigger than the remaining side)
a+b>c && b+c>a && c+a>b
  • since a<=b<=c, the checking above can be rewritten as
a+b>c
  • c must be even (otherwise, the square root result will be odd and d wont be an integer)
  • if c is even, a and b must have the same parity.  Because (1) can be rewritten as:
2(d^2 + (c/2)^2) = a^2 + b^2
  • pre-calculate even perfect sqaures instead of doing square root and check if dividable by 2

Tried to implement it with Scala.  The code is concise and under 30 lines (with comments!).  However, running it on my i5 4120 will probably take weeks to complete. And that is with parallelism and all CPU cores at 100%.

Time to re-install OpenCL SDK and do some coding in C/C++.




No comments: