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,3

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).

Links

Table of n, a(n) for n=1..87.

Example

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).

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<len, i++; s=Subsets[edgePts, {k}, {i}][[1]]; If[Intersection@@hidden[[s]]=={}, done=True; Break[]]]]; k, {n, 2, 11}]]

Crossrefs

Sequence in context: A379265 A025792 A119447 * A077463 A084556 A084506

Adjacent sequences: A157717 A157718 A157719 * A157721 A157722 A157723

Keyword

hard,nonn

Author

T. D. Noe, Mar 06 2009

Extensions

More terms from Lars Blomberg, Nov 06 2014

Status

approved