A157720 Least number of edge lattice points from which every point of a square n x n lattice is visible.

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

Offset: 1

Author

T. D. Noe, Mar 06 2009

Keywords

• hard
• nonn

Comments

This sequence, which is easier to compute than A157639, provides an upper bound for A157639. By using every other point on one side of the lattice, it is easy to see that a(n) <= ceiling(n/2).

Examples

			a(3) = 2 because all 9 points are visible from (1,1) or (1,2).
a(5) = 3 because all 25 points are visible from (1,1), (1,2), or (1,4).
a(11)= 4 because all 121 points are visible from (1,1), (1,2), (2,1), or (1,4).
a(27)= 5 because all 729 points are visible from (1,1), (1,2), (2,1), (1,3), or (1,4).
		

Programs

Mathematica

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

Extensions

More terms from Lars Blomberg, Nov 06 2014