Question

Given a binary quadratic form with negative discriminant, such as $3x^{2} + y^{2} = k$, is there an efficient algorithm to compute a value $k$ (or all the values) for which the form has exactly $n$ integer solutions?

Answer 1

You should clarify what you mean by "efficient algorithm" and "to compute". In general you can express the number of representations as a linear combination of Dirichlet coefficients of certain Hecke $L$-functions. The Hecke characters are the unramified Hecke characters of $\mathbb{Q}(\sqrt{-d})$, where $-d$ is the discriminant of the quadratic form (there are complications when $-d$ is not a fundamental discriminant). The Dirichlet coefficients are multiplicative and can be described explicitly in terms of the Hecke characters. In the end you will have a formula in terms of the prime ideal decomposition of $(k)$ in $\mathbb{Q}(\sqrt{-d})$, and the values of the Hecke characters at the prime ideals participating in the decomposition. So yes, there is an algorithm, but it might not be efficient for your taste because you need to decompose into prime ideals in $\mathbb{Q}(\sqrt{-d})$ and consider about $\sqrt{|d|}$ Hecke characters (imposing "generalized congruence restrictions" on the prime ideals).

A good introduction into these things is Cox: Primes of the form $x^2+ny^2$.

Answer 2

If there is one value of $k$ where the form has exactly $n$ solutions, there are infinitely many values of $k$. This is because, if $ax^2+bxy+cx^2=k$ has $n$ solutions, and $p$ is a prime which is inert in $\mathbb Q(\sqrt{b^2-4ac})$ and does not divide $k$, then $ax^2+bxy+cy^2=kp$ has $n$ solutions as well, because $ax^2+bxy+cy^2\equiv 0$ mod $p$ has just the trivial solution, so $x$ and $y$ must be multiples of $p$.

Since there are infinitely many inert primes, one can get infinitely many different values of $k$.