[Coco] Project Euler and the Coco

[John]

The reason you get asked for a*b*c is the web page only has a single input
box to verify your answer.  Kind of a mundane answer (but leads to a whole
realm of alternate solutions that may share the same prime factors...).

John

-----Original Message-----
From: coco-bounces at maltedmedia.com [mailto:coco-bounces at maltedmedia.com] On
Behalf Of Arthur Flexser
Sent: Saturday, November 15, 2008 2:26 PM
To: CoCoList for Color Computer Enthusiasts
Subject: Re: [Coco] Project Euler and the Coco

Better yet, use a+1 as the lower bound for b if a > 250, since b must be
strictly greater than a.  Changing the lower bound if a > 250 is not only
efficient, but also necessary to avoid violating the requirement that b > a.

(I'd originally considered the possiblity that b could equal a, overlooking
the
problem specification that b>a.  In any case, b could not equal a, since
that
would make c equal to a times the square root of 2, inconsistent with the
requirement that c be an integer.)  Similarly, if a <= 250, use (501-a) as
the
lower bound for b, since b must be at least one greater than (500-a).  Also
on
the same theme, the requirement that c be at least one greater than b means
the
upper bound for b should be (999-a)/2 rather than (1000-a)/2.

I'd do it as two successive FOR/NEXT loops, the first taking A from 2 to 250
with B ranging from (501-A) to (999-A)/2, and the second taking A from 251
to
333 with B ranging from (A+1) to (999-A)/2.  (Come to think of it, the upper
bound for A should be 332 rather than 333, since if A were 333, then the
minimums for B and C would be 334 and 335, which adds to 1002.)

A more satisfying comparison than how many iterations are needed to find the
solution would be how many iterations are necessary to search the parameter
space to completion, in order to verify that there is only one solution.

It is a bit puzzling that the problem asks for the value of a*b*c for no
obvious
reason.  The only explanation that occurs to me is that it is possible to
deduce
this value mathematically without doing a trial-and-error search of all
eligible
a-b-c combinations and without knowing the individual values of a, b, and c
that
constitute the complete solution.  (By the way, what ARE those values?)

Art

On Sat, 15 Nov 2008, Arthur Flexser wrote:

> Mark,
> 
> While I agree that b > (500-a), (and nice work to you, too), b must also
be
> greater than or equal to a.  So, for maximum efficiency, the lower bound
of b
> should be either a or (500-a), whichever is greater.  That is, use a as
the
> lower bound if a > 250, and (500-a) as the lower bound otherwise, to save
yet
> more iterations when a is between 250 and 333.
> 
> Art
> 
> 
> On Sat, 15 Nov 2008, Mark McDougall wrote:
> 
> > Arthur Flexser wrote:
> > 
> > > The ascending length requirement means that B must
> > > take up no more than half of the remaining board, or (1000-A)/2.  
> > 
> > (a^2 + b^2)= c^2
> > (a^2 + b^2) = (a+b)^2 - 2ab = c^2
> > therefore, a+b > c
> > a + b > (1000 - a - b)
> > 2a + 2b > 1000
> > (a+b) > 500
> > ie, b > (500-a)
> > 
> > and using Arthur's observation (nice work)
> > 
> > FOR B=500-A TO (1000-A)/2
> > 
> > reduces the number of iterations to find the solution to 10,174 from the

> > original 66,174 iterations - a massive 85% reduction!
> > 
> > Regards,
> > 
> > -- 
> > |              Mark McDougall                | "Electrical Engineers do
it
> > |  <http://members.iinet.net.au/~msmcdoug>   |   with less resistance!"
> > 
> > --
> > Coco mailing list
> > Coco at maltedmedia.com
> > http://five.pairlist.net/mailman/listinfo/coco
> > 
> 
> 
> --
> Coco mailing list
> Coco at maltedmedia.com
> http://five.pairlist.net/mailman/listinfo/coco
> 



--
Coco mailing list
Coco at maltedmedia.com
http://five.pairlist.net/mailman/listinfo/coco