A157639 Least number of lattice points from which every point of a square n X n lattice is visible.

1, 1, 1, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4

Offset: 1

Author

T. D. Noe, Mar 03 2009

Keywords

• hard
• nice
• nonn

Comments

Adhikari and Granville give bounds on the size of a(n).

From Jon E. Schoenfield, Aug 03 2009, Aug 09 2009, Sep 02 2009: (Start)

Consider an arbitrarily large lattice. Define S1 as the square having both X and Y in the closed interval [1,3]. From a single viewpoint at (2,2), every lattice point on or inside S1 is visible. S1 (including its edges) covers 3 rows X 3 columns of lattice points, so a(3)=1. Also, since an n-row X n-column subset of S1 that includes the one viewpoint can be selected for n=1 and for n=2, this 1-viewpoint example is sufficient to show that a(n)=1 for n = 1..3.

Define S2 as the square having both X and Y in [1,5]. Every lattice point in S2 is visible from at least one of the two viewpoints (3,1) and (3,4). S2 covers 5 rows X 5 columns of points, so a(5) <= 2. Since a 4-row X 4-column subset of S2 that includes the two viewpoints can also be selected, a(4) <= 2. Since no 1-viewpoint solution exists for n > 3, we have a(n)=2 for n=4 and n=5.

Proceeding similarly, every lattice point where X and Y are both in [1,23] is visible from at least one of the three viewpoints (14,14), (15,14), and (14,15), so a(n) <= 3 for n = 2..23. Since no 2-viewpoint solution exists for n > 5, we have a(n)=3 for n = 6..23.

Together, the three 4-viewpoint solutions {(20,20), (21,20), (20,21), (21,21)}, {(43,51), (72,65), (58,80), (57,66)}, and {(28,34), (105,105), (34,99), (99,40)} are sufficient to show that a(n) <= 4 for n = 24..132: in these solutions, every lattice point where X and Y are both in [1,m], where m = 40, 128, and 132, respectively, is visible from at least one viewpoint, and all four viewpoints would fit in a k-row X k-column subset of the m-row X m-column square, for k as small as 2, 30, and 78, respectively. Thus these three solutions demonstrate that a(n) <= 4 for the overlapping ranges n = 2..40, n = 30..128, and n = 78..132, respectively. Since (per an exhaustive search) no 3-viewpoint solution exists for n = 24..132, we have a(n)=4 for n = 24..132.

Per exhaustive search, no 4-viewpoint solution exists for n=133, so a(133)=5.

In summary: a(1..3)=1, a(4..5)=2, a(6..23)=3, a(24..132)=4, a(133)=5. (End)

Examples

			a(3) = 1 because all 9 points are visible from the central (2,2) point.
a(4) = 2 because all 16 points are visible from (1,2) or (2,1).
a(6) = 3 because all 36 points are visible from (1,1), (1,2), or (2,1).
a(24)= 4 because all 576 points are visible from (1,1), (1,2), (1,3), or (2,24).
		

Links

• Sukumar Das Adhikari and Andrew Granville, Visibility in the Plane
• Eric Weisstein's World of Mathematics, Visible Point

Crossrefs

Cf. A141224.

Programs

Mathematica

Table[sees=Table[{},{n^2}]; Do[pt1=(c-1)*n+d; lst={}; Do[pt2=(a-1)*n+b; If[GCD[c-a,d-b]<2, AppendTo[lst,pt2]], {a,n}, {b,n}]; sees[[pt1]]=lst, {c,n}, {d,n}]; done=False; k=0; While[ !done, k++; len=Binomial[n^2,k]; i=0; While[i
				

Extensions

Terms after a(24) from Jon E. Schoenfield, Aug 03 2009