login
Minimum number of points of the square lattice falling strictly inside a circle of radius n.
8

%I #83 Nov 27 2021 11:07:00

%S 0,1,9,25,45,69,108,145,193,248,305,373,437,517,608,697,793,889,1005,

%T 1124,1245,1369,1510,1649,1789,1941,2109,2278,2449,2617,2809,2997,

%U 3202,3405,3613,3834,4049,4281,4509,4762,5013,5249,5521,5785,6068,6348,6621,6917

%N Minimum number of points of the square lattice falling strictly inside a circle of radius n.

%C Due to the symmetry and periodicity of the square lattice it is sufficient to explore possible circles with center belonging to the triangle with vertices (0,0), (1/2,0), and (1/2,1/2).

%C The different regions for the centers producing constant numbers of lattice points inside circles of radius n seem to become very complex and irregular as n increases (see density plots in Links).

%H Robert G. Wilson v, <a href="/A291259/b291259.txt">Table of n, a(n) for n = 0..125</a>

%H Andres Cicuttin, <a href="/A291259/a291259.pdf">Plots of regions for centers of circles of several radii n enclosing constant number of lattice points</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/CircleLatticePoints.html">Circle Lattice Points</a>

%F a(n) ~ Pi*n^2.

%F a(n) <= A051132(n). - _Joerg Arndt_, Oct 03 2017

%e From _Arkadiusz Wesolowski_, Dec 18 2017 [Corrected by _Andrey Zabolotskiy_, Feb 19 2018]: (Start)

%e For a circle centered at the point (x, y) = (1/2, 0) with radius 6, there are 108 lattice points inside the circle.

%e Possible (but not unique) choices for the centers of the circles for radii up to 20 are given below.

%e .

%e . Poss. center Points in

%e . x y Radius the circle

%e . ----- ----- ------ ----------

%e . 0 0 1 1

%e . 0 0 2 9

%e . 0 0 3 25

%e . 0 0 4 45

%e . 0 0 5 69

%e . 1/2 0 6 108

%e . 0 0 7 145

%e . 0 0 8 193

%e . 1/5 0 9 248

%e . 0 0 10 305

%e . 0 0 11 373

%e . 0 0 12 437

%e . 0 0 13 517

%e . 1/4 0 14 608

%e . 0 0 15 697

%e . 0 0 16 793

%e . 0 0 17 889

%e . 0 0 18 1005

%e . 1/2 1/2 19 1124

%e . 0 0 20 1245

%e (End)

%t (* A291259: Minimum number of points of the square lattice falling strictly inside a circle of radius n. *)

%t (* The three vertices of the Explorative Triangle (ET) *)

%t P1={0,0}; P2={1/2,0}; P3={1/2,1/2};

%t dd2=SquaredEuclideanDistance;

%t (* candidatePointQ[p,n] gives True if "p" is a candidate point, and False otherwise. A candidate point is a point belonging to a circle of radius "n" with center in the ET *)

%t candidatePointQ[p_,n_] := With[{dds={dd2[p,P1],dd2[p,P2],dd2[p,P3]}}, Max[dds]>=n^2>=Min[dds]];

%t (* Check if point "p" falls inside any circle with radius "n" and center in the ET *)

%t innerPointQ[p_,n_] := With[{dds={dd2[p,P1],dd2[p,P2],dd2[p,P3]}}, Max[dds]<n^2];

%t (* The function "candidatePoints[n]" gives the list of points with distance "n" from some point of the ET *)

%t candidatePoints[n_] := Select[Table[{i,j},{i,-n,n+1},{j,-n,n+1}]//Flatten[#,1]&, candidatePointQ[#,n]&];

%t (* The function "centersFromTwoPoints[{{x1,y1},{x2,y2}},n]" gives the centers of the two circles with radius "n" and tangent to the pair of points {x1,y1} and {x2,y2} *) (* Note: if the distance between the two points is less than 2n then the coordinates of the centers are not integers *)

%t centersFromTwoPoints[{{x1_,y1_},{x2_,y2_}},n_] :=

%t Which[x1==x2,

%t Block[{sqrtTerm=Sqrt[4*n^2-(y1-y2)^2]/2},{{x1-sqrtTerm,(y1+y2)/2},

%t {x1+sqrtTerm,(y1+y2)/2}}],

%t y1==y2,

%t Block[{sqrtTerm=Sqrt[4*n^2-(x1-x2)^2]/2},{{(x1+x2)/2,-sqrtTerm+y1},

%t {(x1+x2)/2,sqrtTerm+y1}}], True,

%t Block[{ddxy2=dd2[{x1,y1},{x2,y2}],sqrtTerm}, sqrtTerm=Sqrt[-(ddxy2*(-4*n^2+ddxy2)*(y1-y2)^2)]; Table[{((x1+x2)*ddxy2-sqrtTerm)/(2*ddxy2),(ddxy2*(y1^2-y2^2)+sign*(x1-x2)*sqrtTerm)/(2*ddxy2*(y1-y2))}, {sign,{1,-1}}]]];

%t (* The function "explorativeCenters[pairc, n]" selects the centers of circles of radius "n" of the list "pairc" lying inside the ET *)

%t explorativeCenters[pairc_,n_] := Select[Table[centersFromTwoPoints[pair,n],{pair,pairc}]//Flatten[#,1]&, 0<=#[[1]]<=1/2 && 0<= #[[2]]<=#[[1]]&];

%t a[n_] := If[n==0, 0, Module[{points,pairc,expcent,innerpoints},

%t points = candidatePoints[n];

%t pairc = Select[Subsets[points,{2}], dd2@@#<4n^2&];

%t expcent = explorativeCenters[pairc,n];

%t innerpoints = Count[Table[{i,j},{i,-n,n+1},{j,-n,n+1}]//Flatten[#,1]&, _?(innerPointQ[#,n]&)];

%t Min[Table[Count[points, _?(dd2[#,center]<n^2&)], {center,expcent}]] + innerpoints]];

%t Table[a[n], {n, 0, 20}] (* _Andres Cicuttin_ & _Andrey Zabolotskiy_, Nov 14 2017 *)

%Y Cf. A046109, A051132, A295344.

%K nonn

%O 0,3

%A _Andres Cicuttin_, Aug 21 2017

%E More terms from _Andrey Zabolotskiy_, Nov 17 2017