Re: all representations by ternary quadratic form with nonnegative coefficients

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 <
[email protected]> 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.
>
>