Re: Is list correct datatype for dynamically building results?

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

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.