A291259 -id:A291259 - cp's OEIS frontend

A123690 Number of points in a square lattice covered by a circle of diameter n if the center of the circle is chosen such that the circle covers the maximum possible number of lattice points.

2, 5, 9, 14, 22, 32, 41, 52, 69, 81, 97, 116, 137, 157, 180, 208, 231, 258, 293, 319, 351, 384, 421, 457, 495, 540, 578, 623, 667, 716, 761, 812, 861, 914, 973, 1025, 1085, 1142, 1201, 1268, 1328, 1396, 1460, 1528, 1597, 1669, 1745, 1816, 1893, 1976, 2053

Offset: 1

Hugo Pfoertner, Oct 09 2006, Feb 11 2007

nonn

a(n) >= max(A053411(n), A053414(n), A053415(n)).

a(n) is an upper bound for the number of segments of a self avoiding path on the 2-dimensional square lattice such that the path fits into a circle of diameter n. A122224(n) <= a(n).

			a(1)=2: Circle with diameter 1 and center (0,0.5) covers 2 lattice points;
a(2)=5: Circle with diameter 2 and center (0,0) covers 5 lattice points;
a(3)=4: Circle with diameter 3 and center (0,0) covers 9 lattice points;
a(4)=14: Circle with diameter 4 and center (0.5,0.2) covers 14 lattice points.

Hugo Pfoertner, Maximum number of points in the square lattice covered by circular disks. Illustrations.

Cf. A123689, A053411, A053414, A053415, A122224, A295344, A291259, A346993, A346994, A346995.

The corresponding sequences for the hexagonal lattice and the honeycomb net are A125852 and A127406, respectively.

(* An exact program using the functions from A291259: *)
Clear[a]; a[n_] := Module[{points, pairc, expcent, innerpoints, cn=Ceiling[n], allpairs},
allpairs = Flatten[Table[{i, j}, {i, -cn, cn+1}, {j, -cn, cn+1}], 1];
points = Select[allpairs, candidatePointQ[#, n]&];
pairc = Select[Subsets[points, {2}], dd2@@#<=4n^2&];
expcent = explorativeCenters[pairc, n];
innerpoints = Count[allpairs, _?(innerPointQ[#, n]&)];
Max[Table[Count[points, _?(dd2[#, center]<=n^2&)], {center, expcent}]] + innerpoints];
Table[a[n/2], {n, 20}] (* Andrey Zabolotskiy, Feb 21 2018 *)

a(21)-a(40) originally conjectured by Jean-François Alcover confirmed and moved to Data and more terms added by Andrey Zabolotskiy, Feb 21 2018

A354702 T(w,h) is an upper bound for the minimum number of grid points in a square grid covered by an arbitrarily positioned and rotated rectangle of width w and height h, where T(w,h) is a triangle read by rows.

Original entry on oeis.org

0, 1, 2, 2, 4, 7, 2, 5, 9, 12, 3, 7, 13, 17, 21, 4, 8, 15, 20, 26, 32, 4, 9, 18, 22, 31, 36, 40, 5, 11, 20, 27, 36, 44, 49, 57, 6, 12, 24, 30, 41, 48, 54, 66, 72, 7, 14, 26, 35, 46, 55, 63, 74, 84, 96, 7, 15, 28, 37, 50, 60, 67, 81, 90, 105, 112, 8, 16, 31, 40, 55, 64, 72, 88, 96, 112, 120, 128

Offset: 1

Hugo Pfoertner, Jun 15 2022

Grid points must lie strictly within the covering rectangle, i.e., grid points on the perimeter of the rectangle are not allowed.
These upper bounds were determined by an extensive random search, the results of which were stable. The proof that none of these bounds can be improved should be possible with a constructive technique such as integer linear programming applied to all combinatorially possible positions of the rectangle relative to the lattice.
A simple random search is implemented in the attached PARI program, which enables a plausibility check of the results for small covering rectangles. It also provides results for the maximum problem. Additional methods were used to obtain the results shown. In particular, angular orientations of the rectangle along connecting lines between all pairs of lattice points and extreme positions of the rectangle, where lattice points are very close to the corners of the rectangle, were investigated, using adjacent terms in A000404.

			The triangle begins:
    \ h 1   2   3   4   5   6   7   8   9   10   11   12
   w \ -------------------------------------------------
   1 |  0;  |   |   |   |   |   |   |   |    |    |    |
   2 |  1,  2;  |   |   |   |   |   |   |    |    |    |
   3 |  2,  4,  7;  |   |   |   |   |   |    |    |    |
   4 |  2,  5,  9, 12;  |   |   |   |   |    |    |    |
   5 |  3,  7, 13, 17, 21;  |   |   |   |    |    |    |
   6 |  4,  8, 15, 20, 26, 32;  |   |   |    |    |    |
   7 |  4,  9, 18, 22, 31, 36, 40;  |   |    |    |    |
   8 |  5, 11, 20, 27, 36, 44, 49, 57;  |    |    |    |
   9 |  6, 12, 24, 30, 41, 48, 54, 66, 72;   |    |    |
  10 |  7, 14, 26, 35, 46, 55, 63, 74, 84,  96;   |    |
  11 |  7, 15, 28, 37, 50, 60, 67, 81, 90, 105, 112;   |
  12 |  8, 16, 31, 40, 55, 64, 72, 88, 96, 112, 120, 128

Hugo Pfoertner, Table of n, a(n) for n = 1..210, rows 1..20 of triangle, flattened
Hugo Pfoertner, Illustrations of the initial terms up to T(5,5).
Hugo Pfoertner, PARI program

Cf. A293330 (diagonal).
Cf. A354492, A354703, A354704, A354705, A355241, A355242.
Cf. A291259 (similar problem for circular disks).
Cf. A000404 (used to check extreme positions of grid points).

PARI
```
\\ See link.
```
PARI
```
\\ See also program link in A355241.
```

A123689 Number of points in a square lattice covered by a circle of diameter n if the center of the circle is chosen such that the circle covers the minimum possible number of lattice points.

Original entry on oeis.org

0, 2, 4, 10, 16, 26, 32, 46, 60, 74, 88, 108, 124, 146, 172, 194, 216, 248, 276, 308

Offset: 1

Hugo Pfoertner, Oct 09 2006

a(n)<=min(A053411(n),A053414(n),A053415(n)).

Using brute force computation and a step size of 1/1000 (though 1/200 suffices), the [conjectured] terms a(21) to a(40) would be: 332, 374, 408, 438, 484, 522, 560, 608, 648, 698, 740, 794, 846, 894, 952, 1006, 1060, 1124, 1184, 1248. - Jean-François Alcover, Jan 08 2018

			a(1)=0: Circle with diameter 1 with center (0.5,0.5) covers no lattice points; a(2)=2: Circle with diameter 2 with center (0,eps) covers 2 lattice points;
a(3)=4: Circle with diameter 3 with center (0.5,0.5) covers 4 lattice points.

Hugo Pfoertner, Minimal number of points in the square lattice covered by circular disks. Illustrations.

Cf. A123690, A053411, A053414, A053415, A122224, A291259.

The corresponding sequences for the hexagonal lattice and the honeycomb net are A125851 and A127405, respectively.

dx = 1/200; y0 = 0; (* To speed up computation, the step size dx is experimentally adjusted and the circle center is taken on the x-axis. *)
cnt[pts_, ctr_, r_] := Count[pts, pt_ /; Norm[pt - ctr] <= r];
a[n_] := Module[{r, pts, innerCnt, an, center}, r = n/2; pts = Select[ Flatten[ Table[{x, y}, {x, -r - 1, r + 1}, {y, -r - 1, r + 1}], 1], r - 1 <= Norm[#] <= r + 1 &]; innerCnt = Sum[If[Norm[{x, y}] < r - 1, 1, 0], {x, -r - 1, r + 1}, {y, -r - 1, r + 1}]; {an, center} = Table[{innerCnt + cnt[pts, {x, y0}, r], {x, y0}}, {x, -1/2, 1/2, dx}] // Sort // First; Print["a(", n, ") = ", an, ", center = ", center // InputForm]; an];
Table[a[n], {n, 1, 20}] (* Jean-François Alcover, Jan 08 2018 *)

A293330 Minimum number of points of the square lattice falling strictly inside a square of side n that is not perfectly aligned with the square lattice.

Original entry on oeis.org

0, 0, 2, 7, 12, 21, 32, 40, 57, 72, 96

Offset: 0

Andres Cicuttin, Oct 06 2017

This kind of sequence is related to the practical problem of detecting regular polygons of a given size in pixellated images. This is why it explicitly excludes the minimum number of points that can be obtained with the singular case of squares that are perfectly aligned with the square lattice. Similarly for A291259 and A292060, the different regions for the centers of squares of side n (with a constant minimum number of lattice points inside them) seem to become very complex and irregular as n increases (see density plots in Links).
I tried several alternative algorithms to compute this sequence but they all involved some numerical procedure without exact results. These terms are estimates obtained with the proposed algorithm which for every square size: (i) makes a discrete exploration of the continuous tridimensional space that determines the container square (two coordinates for the center and one for the orientation), (ii) checks the number of points falling inside, and (iii) picks the lowest obtained number.
In short, these numbers have not been rigorously proved to be correct. - N. J. A. Sloane, Mar 31 2018

Andres Cicuttin, Plots of different regions for the centers of squares of side n with constant minimum numbers of lattice points inside them
Hugo Pfoertner, Illustrations of upper bounds for the terms a(1)..a(25)

Cf. A291259, A292060.

(* This gives a polar function of a k-sides regular polygon with side length "side" *)
PolarPolygonSide[sidelength_, theta_,
   k_] := ((sidelength/2)/Tan[Pi/k])/
   Cos[Mod[theta - Pi/k, 2 Pi/k] - Pi/k];
(* {x,y}: coordinate of the test point,
   phase: angle offset,
   sides: number of sides *)
TruePointInsidePhase[x_, y_, sidelength_, phase_, sides_] :=
  Module[{theta}, theta = ArcTan[x, y] + phase;
   If[x^2 + y^2 == 0, 1,
     If[x^2 + y^2 - (PolarPolygonSide[sidelength, theta, sides]^2) < 0, 1, 0]] // Return];
sides = 4; dstep = 0.025; phasestep = 2 Pi/300;
epsilon = 2Pi*10^-6; (* small initial angle to avoid a perfectly aligned square *)
seq = {};
Do[npoints = {}; k = 0;
Do[Do[Do[
     Do[Do[k =
        k + TruePointInsidePhase[i + di, j + dj, sidelength, phase, sides],
{i, -sidelength - 1, sidelength + 1, 1}],
{j, -sidelength - 1, sidelength + 1, 1}];
     AppendTo[npoints, k];     k = 0;,
{dj, 0, 1/2, dstep}],
{di, 0, 1/2, dstep}],
{phase, epsilon, 2 Pi/sides, phasestep}] // Quiet;
temp = npoints // Min;
AppendTo[seq, temp]; Print[seq // Last], {sidelength, 0, 10, 1}]
Print[seq]
(*
(*This gives the number of points strictly inside a polygone given by
function "PolarPolygonSide" of "sides" sides, side length: "sidelength", centered in (-di,-dj) and rotated by "phasestep" radians wrt to initial orientation: *)
FaeDensityPlot[sides_, sidelength_, di_, dj_, phasestep_] :=
Module[{npoints = {}, kamin = {}, k = 0},
  Quiet[Do[Do[
     Do[k = k +
        TruePointInsidePhase[i + di, j + dj, sidelength, phase,
         sides], {i, -sidelength - 1, sidelength + 1,
       1}], {j, -sidelength - 1, sidelength + 1, 1}];
    AppendTo[npoints, k];
    k = 0;, {phase, 0, (2 \[Pi])/sides, phasestep}]];
  Return[Min[npoints]]]
(*This plots the regions for the centers of squares of side "sidelength" with constant minimum numbers of lattice points inside*)
sidelength=6;
DensityPlot[FaeDensityPlot[4, sidelength, x, y, (2 \[Pi])/300] ,{x, 0, 1/2}, {y, 0, 1/2}, PlotPoints -> 100, PlotRange -> All, ColorFunction -> "DeepSeaColors", MaxRecursion -> 3, PerformanceGoal -> "Quality", PlotTheme -> "Detailed", PlotLegends -> Automatic]
*)

a(n) ~ n^2.

A295344 Maximum number of lattice points inside and on a circle of radius n.

Original entry on oeis.org

1, 5, 14, 32, 52, 81, 116, 157, 208, 258, 319, 384, 457, 540, 623, 716, 812, 914, 1025, 1142, 1268, 1396, 1528, 1669, 1816, 1976, 2131, 2300, 2472, 2650, 2836, 3028, 3228, 3436, 3644, 3859, 4080, 4314, 4548, 4792, 5038, 5289, 5555, 5818, 6092, 6376, 6668, 6952

Offset: 0

Arkadiusz Wesolowski, Nov 20 2017

nonn

Maximum number of lattice points (i.e., points with integer coordinates) in the plane that can be covered by a circle of radius n.
a(n) >= A000328(n).
Conjecture: sequence contains infinitely many terms that are divisible by 4.

			For a circle centered at the point (x, y) = (1/2, 1/4) with radius 2, there are 14 lattice points inside and on the circle.
.
.     Center             # Pts in/
.    x      y    Radius  on circle
.  -----  -----  ------  ---------
.    0      0       1         5
.   1/2    1/4      2        14
.   1/2    1/2      3        32
.   1/2    1/2      4        52
.    0      0       5        81
.   1/2    1/3      6       116
.   2/5    1/5      7       157
.   1/2    1/2      8       208
.   1/2    2/9      9       258
.  20/47  19/56    10       319
.   1/2    1/2     11       384
.  11/23   7/20    12       457
.   1/2    1/2     13       540
.  10/21   3/13    14       623
.   1/2    1/2     15       716
.   1/2    1/2     16       812
.   2/5    2/5     17       914
.   3/8    5/14    18      1025
.   1/2    1/6     19      1142
.   9/19   8/17    20      1268

B. R. Srinivasan, Lattice Points in a Circle, Proc. Nat. Inst. Sci. India, Part A, 29 (1963), pp. 332-346.

Cf. A000328, A123690, A291259.

L=List([]); for(n=0, 47, if(n>0, j=5, j=1); g=0; h=0; f=ceil(Pi*n^2); for(d=2, floor(f/2), for(c=1, floor(d/2), if(gcd(c, d)==1, for(e=d, d+1, if(e/f<=1/2, a=c/d; b=e/f; if(a+b>=1/2, t=0; for(x=-n, n+1, for(y=-n, n+1, z=(a-x)^2+(b-y)^2; if(z<=n^2,t++))); if(t>j, j=t; if(a>=b, g=a; h=b, g=b; h=a)))))))); print("a("n") = "j", the center of the circle is at point ("g", "h")."); listput(L, j)); print(); print(Vec(L));

a(n) = Pi*n^2 + O(n), as n goes to infinity.

a(n) = A123690(2*n) for n >= 1.

a(10) corrected by Giovanni Resta, Nov 24 2017

A292060 Minimum number of points of the square lattice falling strictly inside an equilateral triangle of side n.

Original entry on oeis.org

0, 0, 0, 2, 4, 8, 12, 17, 23, 30, 37

Offset: 0

Andres Cicuttin, Sep 08 2017

Due to the symmetry and periodicity of the square lattice it is sufficient to explore possible equilateral triangles with center belonging to the triangular region with vertices (0,0), (1/2, 0), and (1/2, 1/2), and for every center the orientations between 0 and 2*Pi/3 radians must be explored. A simple strategy to obtain this sequence is to explore many triangles with centers and orientations in the previously described regions and count the points falling strictly inside the triangles, then picking the minimum number obtained. In the given Mathematica program the explored triangles are generated by regularly moving its center with constant increment in both main orthogonal directions, and for every center different orientations are generated with constant angular step increment.
Is there any criterion to determine how small should be the pitch and the angular increment in order to catch an equilateral triangle with the smallest possible number of points for a given side length n?
The different regions for the centers producing constant minimum numbers of lattice points inside equilateral triangles of side length n seem to become very complex and irregular as n increases (see density plots in Links).

Andres Cicuttin, Plots of regions for centers of equilateral triangles of several side lengths n enclosing constant minimum number of lattice points

Cf. A291259, A292896.

(* This gives a polar function of a "k" sides polygon with side length "sidelength" and vertical rightmost side  *)
PolarPolygonSide[sidelength_, theta_, k_] := ((sidelength/2)/Tan[Pi/k])/Cos[Mod[theta - Pi/k , 2 Pi/k] - Pi/k];
(* uncomment next to generate and plot different polygons *)
(* Manipulate[PolarPlot[PolarPolygonSide[sidelength, theta + phase, sides], {theta, 0, 2 Pi}, PlotRange -> sidelength, GridLines -> {Range[-sidelength, sidelength] + di, Range[-sidelength, sidelength] + dj}], {sidelength, 1, 10, 1}, {sides, 3, 30, 1}, {phase, 0, 2 Pi/3, 2 Pi/300}, {dj, 0, 1/2, 0.01}, {di, 0, 1/2, 0.01}] *)
(* This function gives 1 if the point of coordinates (x,y) is strictly inside a polygon given by PolarPolygonSide[sidelength, theta, sides] rotated by "phase", and 0 otherwise *)
TruePointInsidePhase[x_, y_, sidelength_, phase_, sides_] :=
  Module[{theta},
   theta = ArcTan[x, y] + phase;
   If[x^2 + y^2 == 0, 1,
     If[x^2 + y^2 - (PolarPolygonSide[sidelength, theta, sides]^2) <
       0, 1, 0]] // Return];
sides = 3; (* number of sides of the polygon *)
(* The following step increments seem to be small enough for sidelengths up to 10 *)
dstep = 0.01; (* scanning step on x and y *)
phasestep = 2 Pi/3000; (* orientation angular increment step *)
seq = {};
Do[
npoints = {}; k = 0;
Do[Do[Do[
     Do[Do[
       k =
        k + TruePointInsidePhase[i + di, j + dj, sidelength, phase,
          sides]
       , {i, -sidelength - 1, sidelength + 1, 1}], {j, -sidelength -
        1, sidelength + 1, 1}];
     AppendTo[npoints, k];
     k = 0;
     , {dj, 0, 1/2, dstep}], {di, 0, 1/2, dstep}], {phase, 0, 2 Pi/3,
    phasestep}] // Quiet;
temp = npoints // Min;
AppendTo[seq, temp];
, {sidelength, 0, 10, 1}]
seq

a(n) ~ (1/4)*sqrt(3)*n^2.

A356435 a(n) is the minimum number of Z x Z lattice points inside or on a circle of radius n^(1/2) for any position of the center of the circle.

Original entry on oeis.org

0, 2, 4, 8, 10, 14, 16, 20, 22, 26, 29, 32, 32, 39, 41, 44, 46, 51, 52, 56, 58, 62, 66, 69, 69, 74, 79, 82, 85, 88, 88, 92, 96, 100, 103, 106, 108, 113, 116, 119, 120, 122, 124, 132, 135, 138, 141, 143, 145, 146, 152, 158, 160, 164, 164, 166, 172, 175, 179, 181, 184, 186, 189, 193, 194, 199

Offset: 0

Bernard Montaron, Aug 07 2022

nonn

a(n) <= A057655(n).

The terms of square index of this sequence are such that a(n^2) = A123689(2n) >= A291259(n), e.g., a(9) = 26 = A123689(6) >= A291259(3) = 25.

			For n = 1 the minimum number of Z x Z lattice points inside the circle is a(1) = 2. The minimum is obtained, for example, with the circle centered at x = 0.1, y = 0.

Cf. A057655, A123689, A291259.

Let N(u,v,n) be the number of integer solutions (x,y) of (x-u)^2 + (y-v)^2 <= n. Then a(n) is the minimum of N(u,v,n) taken over 0 <= u <= 1/2 and 0 <= v <= u. Due to the symmetries of the square lattice one can limit the position (u,v) of the circle center within this triangle. The terms of the sequence were found by "brute force" search of the minimum of N(u,v,n) for (u,v) running through the triangular domain above.

cp's OEIS Frontend

A123690 Number of points in a square lattice covered by a circle of diameter n if the center of the circle is chosen such that the circle covers the maximum possible number of lattice points.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A354702 T(w,h) is an upper bound for the minimum number of grid points in a square grid covered by an arbitrarily positioned and rotated rectangle of width w and height h, where T(w,h) is a triangle read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

PARI

A123689 Number of points in a square lattice covered by a circle of diameter n if the center of the circle is chosen such that the circle covers the minimum possible number of lattice points.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A293330 Minimum number of points of the square lattice falling strictly inside a square of side n that is not perfectly aligned with the square lattice.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A295344 Maximum number of lattice points inside and on a circle of radius n.

Views

Author

Keywords

Comments

Examples

References

Crossrefs

Programs

PARI

Formula

Extensions

A292060 Minimum number of points of the square lattice falling strictly inside an equilateral triangle of side n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A356435 a(n) is the minimum number of Z x Z lattice points inside or on a circle of radius n^(1/2) for any position of the center of the circle.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula