I am trying to find circles on lattice points with exactly $n$ lattice points on its circumference. Schinzel's Theorem only gives one instance for each $n$ and it does not necessarily have the smallest radius. There are two general problem I am trying to solve:
Given $n$, find the circle with smallest radius (arbitrary center).
Given $n$ and $R$, find all circles with radius $r<R$.
The problem can be solved by properties of sum of squares function when the center is on a lattice point (origin). But I found few references when the center is on the axis $(x_0,0)$ or even off the lattice. I also know how to reduce the problem to the same as above, given a center with fraction coordinates. But I do not know the search space for all the possible centers, and this becomes the bottleneck for both problems.
Any references and hints are appreciated.
I wrote some Python code to find minimal lattice circles for a puzzle I was solving. See Enigma 136: Twelve-point square, where I give a list of minimal lattice circles with radius less than 1800 (and some other ones that are known to be minimal), along with some other circles which I've found, but are not necessarily minimal.
The smallest unverified circles are for n=29 and n=31 points on the circumference.