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

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

On Fri, Oct 06, 2023 at 10:38:53AM +0200, Bill Allombert wrote:
> > 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.
... but suboptimal, we should start by the largest i, so that P is as
small as possible!

foursquaref(n)=
{
  forstep(i=sqrtint(n),1,-1,
    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))))));
}

Cheers,
Bill.