|
Search: id:A157720
|
|
|
| A157720 |
|
Least number of edge lattice points from which every point of a square n x n lattice is visible. |
|
+0
4
|
|
| 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
(list; graph; listen)
|
|
|
OFFSET
|
1,3
|
|
|
COMMENT
|
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).
|
|
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: A096143 A025792 A119447 this_sequence A077463 A084556 A084506
Adjacent sequences: A157717 A157718 A157719 this_sequence A157721 A157722 A157723
|
|
KEYWORD
|
hard,more,nonn
|
|
AUTHOR
|
T. D. Noe (noe(AT)sspectra.com), Mar 06 2009
|
|
|
Search completed in 0.002 seconds
|
