Re: Is list correct datatype for dynamically building results?

[Charles Greathouse <crgreathouse@gmail.com>]

Also, restarting the forprime loop is not efficient. So

least_neg_legendre_primes(p, s=2, c=1)=

{

  my(v=vector(c), i);

  forprime(q=s,,

    if(kronecker(q,p)==-1,

      v[i++] = q;

      if(i==c, return(v))

    )

  );

}

addhelp(least_neg_legendre_primes, "least_neg_legendre_primes(p, {s=2}, {c=1}): Finds the smallest c primes n >= s with Legendre symbol -1 at prime p.");

or

least_neg_jacobi(p, s=2, c=1)=

{

  my(v=vector(c), i);

  for(n=s,oo,

    if(kronecker(n,p)==-1,

      v[i++] = n;

      if(i==c, return(v))

    )

  );

}

addhelp(least_neg_jacobi, "least_neg_jacobi(p, {s=2}, {c=1}): Finds the smallest c numbers n >= s with Jacobi symbol -1 at prime p.");

or

least_nonresidues(p, s=2, c=1)=

{

  my(v=vector(c), i);

  forfactored(n=s,10^9 /* oo not allowed here, there are more careful ways of handling this */,

    my(Q=n[2][,1]);

    for(j=1,#Q,

      if(kronecker(Q[j],p)==-1,

        v[i++] = n[1];

        if(i==c, return(v));

        break

      )

    )

  );

}

addhelp(least_nonresidues, "least_nonresidues(p, {s=2}, {c=1}): Finds the smallest c nonresidues to a prime p.");

Leaving the composite versions as an exercise here, but the idea is the same, just factor and search.

On Sat, Jul 22, 2023 at 5:28 AM Bill Allombert <Bill.Allombert@math.u-bordeaux.fr> wrote:

On Sat, Jul 22, 2023 at 09:35:24AM +0200, Karim Belabas wrote:
> * hermann@stamm-wilbrandt.de [2023-07-22 02:10]:
> [...]
> > Until now I used "smallest_qnr(n)" function to return smallest quadratic
> > non-residue (mod n).
> >
> > I extended definition to return c smallest quadratic non-residues:
> >
> > ? smallest_qnr(m,s=2,c=1) = {
> >     l=List();
> >     for(c=-c,-1,
> >      forprime(t=s, oo,
> >         if(kronecker(t, m)==-1,
> >           listput(l,t);
> >           s=t+1;
> >           break()
> >         )
> >       )
> >     );
> >     l
> >   };
>
> That function doesn't quite achieve what you claim. Precisely, it
> returns the smallest integers t with kronecker(t, m) = -1, which
> are the same as quadratic non residues only if m is prime.

Also even if m is prime, your function only return the smallest _prime_ quadratic
non-residues.

It is an easy result that the smallest positive quadratic non-residue is a prime number
(since at least one of its factors must be a non-residue), but it is not true for subsequent
ones, obviously.

Cheers,
Bill.