3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ This is Project Euler #513. $\endgroup$ – rogerl Apr 27 '15 at 14:01
  • $\begingroup$ @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. $\endgroup$ – Nicolás Siplis Apr 27 '15 at 14:04
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Nicolás Siplis Apr 27 '15 at 18:42
  • $\begingroup$ @NicolásSiplis: it is not a typo - by $m=\square+\square$ I mean that $m$ can be expressed as the sum of two squares. $\endgroup$ – Jack D'Aurizio Apr 27 '15 at 18:52
  • $\begingroup$ 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. $\endgroup$ – Nicolás Siplis Apr 27 '15 at 18:56
  • $\begingroup$ 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. $\endgroup$ – Nicolás Siplis Apr 27 '15 at 20:49
  • 1
    $\begingroup$ 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! $\endgroup$ – Nicolás Siplis Apr 30 '15 at 3:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.