Let a, b, and m be positive whole numbers. Required is a fast algorithm for evaluating Σ_k=0..m floor(ka/b), floor(x) being the greatest integer that does not exceed the real number x.

(In reply to Solution (part 1) by Tristan)

Well, I'm back, but I still haven't finished this solution.  I seem to have hit a bit of a snag.  As I noted at the end of my last comment, the triangle is not necessarily a lattice triangle.  Pick's theorem (thanks to Hugo for naming it) doesn't quite work unless it's a lattice triangle.

And so, this is where, I suspect, the theoretical math ends, and the algorithm-writing begins.  The solution may not be as clean or fast as I expected (as in a closed expression).

I hope to write more later.

Posted by Tristan on 2005-12-28 00:40:01