**From New Scientist #1280, 19th November 1981** [link]

“Take a large sheet of ordinary graph-paper,” said Professor Mortis, “and draw a circle with centre at any point you like. Now mark with a tiny blob any place where the circle exactly cuts one of the juncs of the graph-paper. … What? … A junc is where a north-south line cuts an east-west line, of course. … Right. … Then cut out any square you like from the graph paper. … Yes, the square can be of any size and orientation you choose… Next, count the blobs on the square. … Yes, a blob on the edge counts as on the square. … If there are fewer than 12 blobs, start again. But if there are 12 or more blobs, work out the area of the square.”

If the graph-paper is ruled at 1cm intervals, what is the smallest area I can end up with?

[enigma136]

### Like this:

Like Loading...

I didn’t solve this one programatically.

Solution:The smallest square has an area of 45 cm².The smallest circle that passes through 12 lattice points has radius r = 5/√2 (≈ 3.54), and is centred at a point in the middle of a grid square. (See [ http://demonstrations.wolfram.com/LatticeCircles/ ]).

So by enclosing this circle in a square we can manage a square with area (2r)² = 50 cm².

However, we don’t need to enclose the entire circle in the square, just the lattice points. The red square in the diagram below has 8 of the lattice points on the edge of a square with edge length 7, and so has an area of 49 cm².

But the blue square also has 8 of the lattice points on the edge of the square and has an area of 45 cm².

Wolfram Alpha has an interesting page on Lattice Circles [ http://mathworld.wolfram.com/CircleLatticePoints.html ].

Based on the observation that any three points define a circle, and we only need to consider Lattice Circles whose centre lies within the triangle defined by (0, 0), (1/2, 0), (1/2, 1/2), this program produces lattice circles of increasing radius by looking at lattice points within a certain distance of this triangle and then choosing three of the potential lattice points, finding out where the centre of the circle defined by those points lies, and if it is within the required triangle we determine how many of the potential lattice points are at the same distance.

The lattice circles for each radius interval are collected and returned in order of increasing radius size, then the interval is increased to find the next batch of circles, and so on, until we find the first circle with the required number of lattice points.

The program uses the best implementation of rational numbers it can find. I found that using

gmpyrationals underCPythonwas faster than usingPythonrationals underPyPy.This program finds a minimal sized circle with 12 lattice points in 88ms, and confirms that it has a radius of 5/√2, and is centred at (1/2, 1/2), and matches the diagram given above.

Consequently I've moved this puzzle from the "Not Solved Programatically" section of the "Notable Enigmas" page to the "Partial Programmatic Solution" section.

I've used (a variation on – see below) this program to check circles up to a radius of 1800 and here's a table of the minimal Lattice Circles I've found so far:

Note that the minimal circles with 17 and 19 points have the same radius, as do the minimal circles with 21 and 22 points.

Using a different program which checks for lattice circles with a known centre (which is much faster), I’ve checked all the centres found above up to (at least) radius 5000, and here are additional lattice circles that I’ve found where

n ≤ 100orr ≤ 100,000, but I can’t guarantee that these are the smallest possible radius:The numerators of the squared radii in the smallest circles I’ve found (so far) are all products of powers of 5, 13, 17 and 29. These are all primes of the form

(4k + 1), known asPythagorean Primes.I’m keeping a full list of lattice circles that I’ve found at [ https://github.com/enigmatic-code/lattice_circles ].

The program given above works OK when the radius is small, but as the radius gets larger it soon gets bogged down.

The following program is a refinement of the method used in the program above that considers fewer of the lattice points when searching for circles, and so runs much faster. (I’ve used it to increase the search space for the minimal lattice circles given above).

For example, if we are looking for lattice circles with 9 or more points on the circumference, then we can consider dividing the circle into quadrants. One of those quadrants must contain 3 of the lattice points, and this is enough to define the circle. So we can reduce the number of lattice points we consider when looking for lattice circles with more than a certain number of points. In general if we consider a 1/

ksector of the circle, it must contain 3 or more points for any lattice circle with 2k+ 1 or more points. So as we find minimal circles we can reduce the size of the sector we consider.The circles we find by this method may not have their centres in the canonical format (0 ≤

y≤x≤ ½), but by reflecting the circle in one or more of the linesx= ½,y= ½,x=y(which don’t change the position of lattice points) we can find an equivalent circle centred in the required triangle.So, when the program is run to find minimal lattice circles. It starts by considering the entire circle, until circles with 3 and 4 points have been found (the one with 3 points has the largest radius), it then switches to considering half of the circle until circles with 5, 6, 7 and 8 points have been found (the one with 7 points has the largest radius), then it switches to considering one quarter of the circle until minimal circles from 9 to 16 points have been found (the one with 13 points has the largest radius), at which stage it can switch to considering just one eighth of the circle.

In fact, this program was able to find all minimal lattice circles with

r< 200 in about an hour, something that would take my first program many days.Another approach I tried was to consider a lattice circle with origin at a rational point. Then by scaling up the circle by the common denominator of the coordinates of the centre we get a larger circle that is centred on a lattice point, and each lattice point that was on the original circle corresponds to a lattice point on the larger circle (although there may be extra lattice points on the larger circle). So, we can find lattice circles by looking for those centred on a lattice point and scaling them down and translating them appropriately. This boils down to finding positive integers that are expressed as the sum of two squares (possibly in multiple ways). While this does give a method of generating lattice circles, I didn’t see an easy way to be sure I’d found a minimal lattice circle, so I didn’t explore this approach further.