[Coco] Project Euler and the Coco

Art Flexser flexser at fiu.edu
Sun Nov 16 18:13:04 EST 2008


In his response to my question of what was his method for saving 40%,
On Sat, 15 Nov 2008, John wrote:

> I had the loops step down by 1:
> FOR A = 333 to 2 STEP -1
> FOR B = 667 TO 334 STEP -1
> 
> That led to the total iterations until the answer was found dropping from
> 40736 to ~24K because the A loop only runs 133 times instead of 198.  Other
> people on this list have greatly optimized my brute force approach which is
> great to see!
> 

One can certain find the answer faster by choosing a starting place for the
search that is close to it.  That's why I mentioned to Mark that I thought a
better comparison than number of iterations to find the answer would be number
of iterations required to do an exhaustive search of the solution space and
verify that there is only one answer.

> I was a little delayed answering since I started thinking about what you
> wrote in an earlier:
> 
> "One formula for generating Pythagorean triangles is to use as sides 2XY,
> (X^2-Y^2), and (X^2+Y^2), where X and Y can be any two integers with X>Y."
> 
> That led to some relatively simple algebra:
> 2xy + (x^2 - y^2) + (x^2 + y^2) =1000
> 2xy +2x^2 = 1000
> x^2 + y = 500
> x(x+y) = 500
> 
> Since x>y, it's pretty easy to look through the factors of 500 and come up
> with x=20, y=5.
> 
> So the answers are
> 2xy = 2*20*5=200
> x^2 - y^2 = 400-25 = 375 
> x^2 + y^2 = 400+25 =  425
> 

Yes, that certainly beats the brute force method.  Though I'm not certain that
that formula for Pythagorean triangles generates all of them, rather than only
some.  So, it may be that some similar problems would not yield to that
approach.

Art





More information about the Coco mailing list