|
%I #11 Aug 13 2020 14:01:06
%S 1,1,3,3,5,6,8,8,11,11,14,15
%N Minimal number of circles needed to intersect all the points of an n X n grid.
%C The n=2 and n=8 cases each have a unique solution.
%C a(13)=18 or 19; a(14)=19 or 20.
%C 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)).
%H Mersenne Forum, <a href="http://mersenneforum.org/showthread.php?t=20492">Circles Puzzle</a>
%H Erich Friedman (archive), <a href="http://web.archive.org/web/20010505221759/https://erich-friedman.github.io/cirpts/">Circles Through Points</a>
%e 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.
%e n=2: 1 circle: v=[[1/2, 1/2, 1/2]];
%e n=4: 3 circles: v=[[3/2, 1/2, 5/2], [3/2, 3/2, 5/2], [3/2, 5/2, 5/2]];
%e 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]];
%e 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]];
%e 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]];
%e 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]];
%e 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]];
%e 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]];
%Y For circular arcs, see A187679.
%K nonn,more
%O 1,3
%A _Robert Gerbicz_, Sep 19 2015
|
