|
|
A157720
|
|
Least number of edge lattice points from which every point of a square n x n lattice is visible.
|
|
3
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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
|
|
|
KEYWORD
|
hard,nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|