On Sun, 13 Jan 2008 11:48:09 +0100, "Nicu Ionita"
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
Yeah, that's a good one, the most I can narrow down the results the better. But if I can figure out the number of triangles without actually constructing them would be the real winner algorithm.
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 ...
I wish it was monotone, but it doesn't seem to be anything, I even plotted the relation cathetus size x number of triangles, but it didn't really show any pattern. It seems there are more likely results, but there are a few of them that looks just random. If you want to see the plotted graph: http://homepages.dcc.ufmg.br/~rafaelc/problem176.png