Nicu Ionita nionita at lycos.de
Sun Jan 13 05:48:09 EST 2008

```Hi Rafael,

I have just two ideas, that could improve your strategy to reduce the
computation time:

1. perhaps there is also a minimum (not only a maximul) for the values you
should try

2. is the function howManyTriangles monotone? If yes, then you could try to
solve:

howManyTriangles n = 47547

by finding an upper n, nmax, where howManyTriangles nmax > 47547, and than
using Euler to reduce the interval (from 12 to nmax, then probably from (12
+ nmax)/2 to nmax, a.s.o)

Then you will have ~ ln nmax computations of the function, which could be
better than computing it from 1 to ...

Nicu Ionita

> -----Ursprüngliche Nachricht-----
> Rafael Almeida
> Gesendet: Samstag, 12. Januar 2008 22:20
>
>
> Hello,
>
> I have been browsing through the problems at projecteuler.net
> and I found one that seemed interesting. It's the problem
> 176, I'll state it
> here:
>
>         The four rectangular triangles with sides (9,12,15),
> (12,16,20),
>         (5,12,13) and (12,35,37) all have one of the shorter sides
>         (catheti) equal to 12. It can be shown that no other integer
>         sided rectangular triangle exists with one of the
> catheti equal
>         to 12.
>
>         Find the smallest integer that can be the length of a cathetus
>         of exactly 47547 different integer sided rectangular
> triangles.
>
> I thought I've solved it nicely, only to find later on that
> my solution was too slow (it has been running for almost
> three days now). While I was creating my solution I used
> literate haskell, which I think helped me a bunch to think
> about the problem. I wrote it originally in portuguese -- the
> portuguese literate version has all the attempts I've made
> until getting to the final one. For posting it here I've
> translated the reasoning around the attempt that solved the
> problem -- although it does it very slow -- into a new .lhs file:
>
>         http://www.dcc.ufmg.br/~rafaelc/problem176.lhs
>
> After some profiling I found out that about 94% of the
> execution time is spent in the ``isPerfectSquare'' function.
> So I began researching about better ways to write that
> functio. Someone pointed to me on #haskell that the C library
> gmp has such a function. So I went ahead and wrote a C
> version of the program using gmp:
>
>         http://www.dcc.ufmg.br/~rafaelc/problem176.c
>
> It's not the prettiest C code, as I did it really quickly,
> simply translating haskell code into C, but I believe it
> works. That C solution has been running for more than one
> hour now and no solution has come up yet.  So I don't think
> it's worthed even writing a faster isPerfectSquare in haskell.
>
> As I was translating from Portuguese to English I revisited
> my logic and I can't see any problems with it. I think the
> problem is only of slowness, really. Does anyone have a
> better idea for how I should try to solve this problem? I'm
> all out of ideas.
>
> []'s
> Rafael
> _______________________________________________