Re: all representations by ternary quadratic form with nonnegative coeff

Hi Bill,

Thank you for a fair point for abandoning the hope for a better algorithm. However, while the given equation is particularly important for me, I wonder if it's possible to have a generic soliver for ternary forms in PARI/GP, similarly to the one for binary forms.

On a minor note, sqrtint(n) in your code can be replaced with sqrtint(n\3).

Regards,

Max

On Sat, Sep 6, 2025 at 3:07 AM Bill Allombert <Bill.Allombert@math.u-bordeaux.fr> wrote:

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.