# Consider the following Diophantine equation: $x^2 + xy + y^2 = n$ [duplicate]

Consider the following Diophantine equation $$x^2 + xy + y^2 = n\,.$$ For a particular positive integer $$n$$, the number of solutions $$\left(x,y\right)$$ such that $$x$$ and $$y$$ are integers is given by the function $$S(n)$$.

The function $$S(n)$$ is not one-to-one. For example, each number $$n$$ in the set $$\{1, 4, 9, 16, 25, 36\}$$ corresponds with $$S(n) = 6$$.

In increasing order, starting from $$n = 1$$, the first $$n$$ such that $$S(n) = 36$$ is $$637$$.

What is the $$500$$th $$n$$ such that $$S(n) = 36$$?

Any precise approach or hint from where I should start the problem?

• Where does this problem come from? Jul 7, 2020 at 14:45
• @EDX surely the RHS would be n+xy no? I hope I'm not making a fool of myself Jul 7, 2020 at 14:46
• Since $x^2+xy+y^2=\left(x+\frac{y}{2}\right)^2+3\left(\frac{y}{2}\right)^2$ we need to consider ring $\mathbb{Z}[\omega]$, where $\omega=\frac{1}{2}+\frac{\sqrt{3}}{2}i$. This numbers are called Eisenstein integers, if I'm not mistaken and your question is how to find number of solutions of the equation $N(z)=n$. Jul 7, 2020 at 14:54
• The solutions are well understood, you should start there: The set of integers $n$ expressible with $n=x^2+xy+y^2$
– Sil
Jul 7, 2020 at 14:55
• Actually $S(637)=36$, while $S(636)=0$. Jul 7, 2020 at 16:07

The function $$S$$ corresponds to OEIS sequence A004016. From there you can get several implementations, for example in PARI:
 {a(n) = if( n<1, n==0, 6 * sumdiv( n, d, (d%3==1) - (d%3==2)))}; /* Michael Somos, May 20 2005 */