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?



Number of solutions of a binary quadratic form.
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$.


