|
%I #6 Nov 06 2014 10:14:43
%S 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,
%T 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,
%U 5,4,5,4,5,4,5,4,5,5,5,4,5,5,5,4,5,5,5
%N Least number of edge lattice points from which every point of a square n x n lattice is visible.
%C 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).
%e a(3) = 2 because all 9 points are visible from (1,1) or (1,2).
%e a(5) = 3 because all 25 points are visible from (1,1), (1,2), or (1,4).
%e a(11)= 4 because all 121 points are visible from (1,1), (1,2), (2,1), or (1,4).
%e a(27)= 5 because all 729 points are visible from (1,1), (1,2), (2,1), (1,3), or (1,4).
%t 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}]]
%K hard,nonn
%O 1,3
%A _T. D. Noe_, Mar 06 2009
%E More terms from _Lars Blomberg_, Nov 06 2014
|
