Re: all representations by ternary quadratic form with nonnegative coefficients

[Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>]

On Wed, Sep 03, 2025 at 09:19:47AM -0400, Max Alekseyev wrote:
> Hello,
> 
> Is there an efficient way to find all solutions in nonnegative integers
> x,y,z to
> xy + xz + yz = n
> for a (large) given integer n?
> Under efficiency I understand anything that is noticeably better than just
> fixing the value of one (smallest) of the variables and solving the
> resulting bivariate quadratic equation by factorization. This approach
> requires O(sqrt(n)) iterations.

What is the expected number of solutions ?

I expect it to be O(sqrt(n)), so an algorithm in O(n^(1/2+epsilon))) for all epsilon>0
should be close to optimal.

Here is one based on the identity (x+y)*(x+z) = x^2 + x*z+ x*y+ y*z

\\ all solutions [x,y,z] with 0<x<=y<=z of  x*y + x*z + y*z = n
allsol(n) =
{
   concat(vector(sqrtint(n),i,
     my(m=i^2+n);
     [[i,d-i,m/d-i]|d<-divisors(m), d*d<=m && d>=2*i && m>=2*d*i]));
}

? allsol(1009)
%238 = [[1,1,504],[1,4,201],[1,9,100],[4,21,37],[5,6,89],[5,17,42],[6,13,49],[7,16,39],[8,21,29],[13,18,25]]

? for(i=1,10,print(i,":",#allsol(10^i)))
1:0
2:2
3:16
4:41
5:214
6:465
7:2336
8:4839
9:24206
  *** concat: Warning: increasing stack size to 16000000.
10:49213

so the number of solution is about sqrt(n)/2

Cheers,
Bill.