# 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)$.

• This is Project Euler #513. – rogerl Apr 27 '15 at 14:01
• @rogerl, It is! It doesn't seem too hard, I guess the trickiest part is translating the combinatorics problem into an algorithm, which I cannot figure out how to do. – Nicolás Siplis Apr 27 '15 at 14:04

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).$$

• This is great! I think your formatting might be a little messed up though. Some of your symbols are replaced by squares which makes it a bit hard to follow the entire process. – Nicolás Siplis Apr 27 '15 at 18:42
• @NicolásSiplis: it is not a typo - by $m=\square+\square$ I mean that $m$ can be expressed as the sum of two squares. – Jack D'Aurizio Apr 27 '15 at 18:52
• Ohh, that explains why when I checked the source code it said \squared. OK, I'll try your second algorithm to start, but I think it's not gonna be feasible since I need to solve the problem for N = 100000. – Nicolás Siplis Apr 27 '15 at 18:56
• As expected, this implementation is considerably faster than the brute force approach, but it takes too long for values such as 100000 or higher. I still think there must be a combinatorics approach. – Nicolás Siplis Apr 27 '15 at 20:49
• After much thought I haven't been able to get a direct formula to calculate the integer triangles with an integer median, so I'll just use your algorithm. It's gonna take a few days more than I thought but I guess that's not such a long wait. Once again, thanks! – Nicolás Siplis Apr 30 '15 at 3:47