Combinatorics - Integer sided triangles with integer median The original problem states: "Given a number N, how many integer-sided triangles $(a,b,c)$ with an integer median $m_{c}$ exist, provided that $a \leq b \leq c \leq N$?".
I've managed to get it down to a problem of combinatorics, but I'm having trouble expressing it mathematically. I'll refer to the function as $T(N)$ from now on.
Given a number N, how many ways are there to distribute a maximum of $3N$ indistinguishable balls into $3$ indistinguishable boxes $(a,b,c)$ in such a way that:
$a \leq b \leq c \leq N$
$a + b > c$
$d = 2a^2+2b^2-c^2$
$\dfrac {\sqrt{d}}{2}\:\in\mathbb{Z}$
By bruteforcing, I know that:
$c\mod 2 \equiv 0$
$a\equiv b\mod 2$
$N < 6 \rightarrow T(N) = 0$
$T(6) = 1 \rightarrow (5,5,6)$
$T(10) = 3 \rightarrow (5,5,6),(5,5,8),(6,8,10)$
$T(100) = 835$
$T(1000) = 149869$
$(a,b,c)\in T(N) \rightarrow (ka,kb,kc) \in T(N),\:k\in\mathbb{N},kc\leq N$
The last property is particularly useful I think, since it means that to figure out $T(N)$ I'd only need a much smaller initial set of triangles (how to find them, however, eludes me). To get these values I had to check almost $N^3$ combinations, so I obviously need a better way to calculate $T(N)$.
 A: We must have:
$$ a\leq b\leq c\leq N,\quad 2a^2+2b^2-c^2 = (2d)^2 $$
but $c$ must be even, so $c=2C$ and:
$$ a^2+b^2=2(d^2+C^2).\tag{1}$$
Now it is useful to recall that the elements of the set $\square+\square$ are exactly the $n$s for which the multiplicity of every prime divisor of the form $4k+3$ is even. Moreover, $n=a^2+b^2$ with $\gcd(a,b)=1$ (also known as primitive representation) is possible if and only if there is no prime of the form $4k+3$ dividing $n$, and:
$$ \begin{eqnarray*}r_2(n) &=& \#\left\{(a,b)\in\mathbb{Z}^2:a^2+b^2=n\right\}\\&=&4\left(\chi_4 * 1\right)(n)\\&=&4\cdot\left(\sum_{\substack{d\mid n\\d\equiv 1\!\!\pmod{\!\!4}}}\!\!\!1\;-\!\!\!\sum_{\substack{d\mid n\\d\equiv 3\!\!\pmod{\!\!4}}}\!\!\!1\right),\end{eqnarray*} $$
so the solutions of $(1)$ may be found by considering all the couples $(a,b)$ such that $0\leq a\leq b\leq N$ and $a,b$ have the same parity, then checking if $\frac{a^2+b^2}{2}$ can be expressed as $d^2+C^2$ with $\frac{b}{2}\leq C\leq\frac{N}{2}$ by factoring $a^2+b^2$ and listing all the possible representations.
Cost: we have to test $\frac{N^2}{2}$ couples. The average value of $r_2(n)$ is $\pi$, so to list the representations and check them does not affect the asymptotic complexity in the average case. The only hard part is to factor every $a^2+b^2$: that can be done by pre-computing all the primes in the range $[1,2N^2]$ together with their (essentially unique) representation as $\square+\square$ in case they belong to the form $4k+1$. Or we may just check if $\frac{a^2+b^2}{2}-C^2$ is a square by testing all the possible $C$s in the range $\left[\frac{b}{2},\frac{n}{2}\right]$. For such a task, a quadratic sieve is useful: for instance, if $\frac{a^2+b^2}{2}-C^2\equiv 3\pmod{7}$ there is no chance that $\frac{a^2+b^2}{2}-C^2$ is a square, so for every couple $(a,b)$ the interval $\left[\frac{b}{2},\frac{n}{2}\right]$ can be sifted, leaving just a few $C$s that deserve to be checked for real. With the quadratic sieve, the expected running time should be around $O\left(N^{5/2}\right)$ and the memory needed $O(N)$.

If memory is not an issue, we may also just put a type-1-mark $(a,b)$
  on every integer of the form $a^2+b^2$ with $1\leq a\leq b\leq N$,
  then put a type-2-mark $(d,C)$ on every number $\leq 2N^2$ of the form
  $2(d^2+C^2)$ with $1\leq d\leq N,1\leq 2C\leq N$, then check, for
  every number having both a type-1 and a type-2 mark, if $a\leq b\leq
 c\leq N$ is fulfilled by pairing a type-1 and a type-2 mark. In this
  case, both the average running time and the memory needed are
  $\color{red}{O(N^2)}$.

Probably, by using hash tables we may also break the $O(N^2)$ barrier, since the  number of integers of the form $\square+\square$ or $2(\square+\square)$ in $[1,2N^2]$ is
$$ O\left(\frac{N^2}{\sqrt{\log N}}\right). $$
