Re: efficient foursquare() and/or threesquare1m4() functions

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

On Fri, Oct 06, 2023 at 10:17:33AM +0200, Bill Allombert wrote:
> You could use
> 
> threesquare(n) = abs(qfsolve(matdiagonal([1,1,1,-n]))[1..3]);
> 
> but it is not faster.
> 
> But you can try this one:
> 
> foursquarep(n)=
> {
>   for(i=1,sqrtint(n),
>     if(ispseudoprime(n-i^2),return(concat(i,threesquare(P-i^2)))))
> }

Sorry, I mixed P and n, it should be

foursquarep(n)=
{
  for(i=1,sqrtint(n),
    my(P=n-i^2);
    if(P%8!=7 && ispseudoprime(P),return(concat(i,threesquare(P)))))
}

> foursquaref(n)=
> {
>   for(i=1,sqrtint(n),
>     my(P=n-i^2, v = valuation(P,2)\2);
>     if (P/4^v%8!=7,
>       my(F=factor(P,2^20)[,1]);
>       if(ispseudoprime(F[#F]),
>         return(concat(i,threesquare(P))))));
> }

This one is OK.
Cheers,
Bill.