A262355 Minimal number of circles needed to intersect all the points of an n X n grid.

1, 1, 3, 3, 5, 6, 8, 8, 11, 11, 14, 15

Offset

1,3

Comments

The n=2 and n=8 cases each have a unique solution.

a(13)=18 or 19; a(14)=19 or 20.

Lim a(n)/n^2=0. Moreover a(n)=O(n^2/sqrt(log(n))) is also true: use concentric circles with center=(0,0), for the squared distance to the points d^2=x^2+y^2<2*n^2 but with Landau's theorem there are only O(u/sqrt(log(u))) integers up to u which are in the form of x^2+y^2, use this for u=2*n^2 to get the theorem (obviously r=d for the radius). A closer center to the grid's center could give fewer circles, for example use center=(floor(n/2),floor(n/2)).

Links

Table of n, a(n) for n=1..12.

Mersenne Forum, Circles Puzzle

Erich Friedman (archive), Circles Through Points

Example

In a two-dimensional vector format the optimal circles are given as the first two terms are the coordinates of the center, the third is the squared radius. If you don't see a particular n value then consider a larger one: for example, as a(9)=a(10), it is enough to give the circles only for n=10. Short Pari code to check these solutions: f(v,n)={a=matrix(n,n,i,j,0);L=length(v);for(i=1,L,x0=v[i][1];y0=v[i][2];r2=v[i][3];for(x=0,n-1,for(y=0,n-1,d2=(x-x0)^2+(y-y0)^2-r2;if(d2==0,a[x+1,y+1]=1)))); s=sum(i=1,n,sum(j=1,n,a[i,j]));print("Using ",L," circles, covered "s," points on the [0,",n-1"]^2 grid.")} Call for example f(v,8), where v is the vector listed for n=8.
n=2: 1 circle: v=[[1/2, 1/2, 1/2]];
n=4: 3 circles: v=[[3/2, 1/2, 5/2], [3/2, 3/2, 5/2], [3/2, 5/2, 5/2]];
n=5: 5 circles: v=[[3/2, 1/2, 5/2], [3/2, 3/2, 5/2], [1/2, 1/2, 25/2], [5/2, 5/2, 5/2], [13/6, 17/6, 85/18]];
n=6; 6 circles: v=[[3/2, 1/2, 5/2], [5/2, 2, 25/4], [5/2, 3, 25/4], [3/2, 9/2, 5/2], [7/2, 1/2, 5/2], [7/2, 9/2, 5/2]];
n=8: 8 circles: v=[[7/2, 7/2, 25/2], [5/2, 5/2, 25/2], [7/2, 7/2, 37/2], [5/2, 9/2, 25/2], [9/2, 5/2, 25/2], [9/2, 9/2, 25/2], [7/2, 7/2, 5/2], [7/2, 7/2, 1/2]];
n=10: 11 circles: v=[[9/2, 9/2, 25/2], [11/2, 11/2, 25/2], [7/2, 7/2, 25/2], [7/2, 11/2, 25/2], [11/2, 7/2, 25/2], [9/2, 9/2, 65/2], [9/2, 9/2, 53/2], [9/2, 9/2, 37/2], [9/2, 9/2, 5/2], [9/2, 1/2, 41/2], [9/2, 17/2, 41/2]];
n=11: 14 circles: v=[[13/2, 13/2, 25/2], [13/2, 9/2, 25/2], [11/2, 11/2, 25/2], [9/2, 13/2, 25/2], [9/2, 9/2, 25/2], [11/2, 11/2, 65/2], [11/2, 11/2, 5/2], [11/2, 11/2, 37/2], [9/2, 11/2, 65/2], [11/2, 9/2, 65/2], [15/2, 15/2, 125/2], [9/2, 9/2, 65/2], [11/2, -1/2, 61/2], [11/2, 21/2, 41/2]];
n=12: 15 circles: v=[[11/2, 11/2, 65/2], [13/2, 11/2, 65/2], [9/2, 11/2, 65/2], [15/2, 11/2, 25/2], [9/2, 11/2, 25/2], [15/2, 11/2, 65/2], [13/2, 11/2, 25/2], [11/2, 15/2, 13/2], [11/2, 7/2, 13/2], [7/2, 11/2, 65/2], [7/2, 11/2, 25/2], [11/2, 19/2, 65/2], [11/2, 3/2, 65/2], [103/10, 11/2, 1517/50], [7/10, 11/2, 1517/50]];

Crossrefs

For circular arcs, see A187679.

Sequence in context: A152772 A089175 A265430 * A325459 A309947 A138373

Adjacent sequences: A262352 A262353 A262354 * A262356 A262357 A262358

Keyword

nonn,more

Author

Robert Gerbicz, Sep 19 2015

Status

approved