3
$\begingroup$

I've come across this problem in my studies. I was wondering if there is a better algorithm for it: Given a fixed positive integer $T$, count the solutions of $$n^2 + n m + m^2 = T$$ where $m$ and $n$ are integers.

I've come up with an $\mathcal{O}(\sqrt{T})$ algorithm.

Basically you can iterate $n$ from $\lfloor\sqrt{T/3}\rfloor$ to $\lfloor 2\sqrt{T/3}\rfloor$ and solve the quadratic equation for $m$ to get all the possible solutions. I won't go into the gory details here. Is there a faster way to count these solutions?

Update Added a TL/DR version of the best answer. Thanks to Will Jagy for the solution and references.

Answer: Let $T = p_1^{a_1}p_2^{a_2}p_3^{a_3}\cdots p_r^{a_r}$ If any $p_i$ is equal to 2 mod 3, and its exponent ($a_i$) is odd, then the number of solutions is zero. If $a_i$ is even, then it does not affect the number of solutions and can be ignored. So assume that all primes dividing $T$ are equal to 1 mod 3. Then the answer is $$p_1^{a_1}p_2^{a_2}p_3^{a_3}\cdots p_r^{a_r} \mapsto 6*(1 + a_1)(1 + a_2)(1 + a_3)\cdots (1 + a_r)$$

$\endgroup$
1
  • 1
    $\begingroup$ Maybe quicker to write it as $(2n+m)^2+3m^2=4T$. Still $O(\sqrt{T})$ but less work for each step. $\endgroup$ – almagest Apr 14 '16 at 13:35
3
$\begingroup$

it is in Dickson's little 1929 book, page 77, exercises 3 and 4. That is, when $m$ has $r$ distinct prime factors, each congruent to $1 \pmod 3,$ then there are exactly $6 \cdot 2^r$ proper representations $m=x^2 + xy + y^2.$ If you want to include all representations and some exponents are larger than one, you may divide $m$ by each square that divides it and add.

You should be aware that, if a prime $q \equiv 2 \pmod 3,$ and the exponent of $q$ in factoring $m$ is odd, then there are no representations at all. If the exponent is even, dividing by $q^2$ does not change the number of representations, so just ignore those: the number of representations of $25$ is the same as the number of representations of $1.$

http://www.abebooks.com/servlet/SearchResults?an=dickson&sts=t&tn=introduction+to+the+theory+of+numbers

enter image description here

enter image description here

$\endgroup$
8
  • $\begingroup$ Clarification: if I have $T = p_1^{a_1} p_2^{a_2} ... p_r^{a_1}$ and all of the $p_i$ are $1$ mod $3$ and some of the $a_i$ are greater than one. Then I'm confused as to what to do to get the total number of solutions (or representations as you call them). Your comment above seems to state that I take $T/(p_i^2)$ and compute the answer and add all of these up?? What would I do for $T = 7^3 \times 13\times19^2$? $\endgroup$ – amcalde Apr 14 '16 at 18:51
  • $\begingroup$ I get $48$ for $T = 7 \times 13 \times 19$ and I get $144$ for $T = 7^3 \times 13\times19^2$. $\endgroup$ – amcalde Apr 14 '16 at 18:56
  • $\begingroup$ Also what about $3$ itself? It looks like (empirically) I can just cross that off too. $\endgroup$ – amcalde Apr 14 '16 at 19:01
  • $\begingroup$ @amcalde, well, compare with raw search. Note that one must divide by squares of composites, so one of the tasks for your $7^3 \cdot 13 \cdot 19^2$ would be $7 \cdot 13.$ $\endgroup$ – Will Jagy Apr 14 '16 at 19:02
  • $\begingroup$ factors of $3$ or $3^k$ do not change the number of representations. $\endgroup$ – Will Jagy Apr 14 '16 at 19:05

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.