Integral triangles and integral medians Consider a triangle ABC where each side has integer length (an integral triangle). Define a median of ABC to be a line segment from a vertex to the midpoint of the opposing side. In the figure below, the red line segments represent the medians. Note that any given triangle has three medians.



Let n be some positive integer. How many non-degenerate integral triangles with each side length less than or equal to n have at least one integral median?

Challenge

Write a program to compute the number of integral triangles with at least one integral median for a given maximum side length n. The order of the side lengths does not matter, i.e. &lt;6,6,5> represents the same triangle as &lt;5,6,6> and should be counted only once. Exclude degenerate triangles such as &lt;1,2,3>.

Scoring

The largest n for which your program can generate the number of triangles in 60 seconds on my machine is your score. The program with the highest score wins. My machine is a Sony Vaio SVF14A16CLB, Intel Core i5, 8GB RAM.

Examples

Let T(N) be the program with input N.

T(1) = 0
T(6) = 1
T(20) = 27
T(22) = 34


Note that T(1) = T(2) = T(3) = T(4) = T(5) = 0 because no combination of integral sides will yield an integral median. However, once we get to 6, we can see that one of the medians of the triangle &lt;5,5,6> is 4, so T(6) = 1.

Note also that T(22) is the first value at which double-counting becomes an issue: the triangle &lt;16,18,22> has medians 13 and 17 (and 2sqrt(85)).

Computing the medians

The medians of a triangle can be calculated by the following formulas:







Current top score: Sp3000 - 7000 points - C
C, brute force - n=6080

This is more a baseline than a serious contender, but at least it should get things started.

n=6080 is as high as I got in a minute of runtime on my own machine, which is a MacBook Pro with an Intel Core i5. The result I got for this value is:


  15041226


The code is purely brute force. It enumerates all the triangles within the size limit, and tests for the condition:

#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;
#include &lt;math.h&gt;

static inline int isSquare(int v) {
    int s = (int)(sqrtf((float)v) + 0.5f);
    return s * s == v;
}

static inline int isMedian(int v) {
    return v % 4 == 0 &amp;&amp; isSquare(v / 4);
}

int main(int argc, char* argv[]) {
    int n = atoi(argv[1]);
    int nTri = 0;
    int a, b, c;

    for (c = 1; c &lt;= n; ++c) {
        for (b = (c + 1) / 2; b &lt;= c; ++b) {
            for (a = c - b + 1; a &lt;= b; ++a) {
                if (isMedian(2 * (b * b + c * c) - a * a) ||
                    isMedian(2 * (a * a + c * c) - b * b) ||
                    isMedian(2 * (a * a + b * b) - c * c)) {
                    ++nTri;
                }
            }
        }
    }

    printf("%d\n", nTri);

    return 0;
}