cp's OEIS Frontend

A157792 Least number of lattice points on one side from which every point of a square n X n lattice is visible.

%I A157792 #18 Feb 16 2025 08:33:09
%S A157792 1,1,2,2,3,3,4,4,4,4,4,5,5,5,6,6,6,7,7,7,8,8,8,9,9,9,10,10,10,11,11,
%T A157792 11,12,12,12,13,13,13,14,14,14,15,15,15,16,16,16,17,17,17,18,18,18,19,
%U A157792 19,19,20,20,20,21,21,21,22,22,22,23,23,23,24,24,24,25
%N A157792 Least number of lattice points on one side from which every point of a square n X n lattice is visible.
%C A157792 That is, the points are chosen from the n points on one side of the n X n lattice. It appears that a(n) = ceiling((n+1)/3) for n > 8.
%H A157792 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/VisiblePoint.html">Visible Point</a>
%F A157792 Conjectures from _Chai Wah Wu_, Aug 05 2022: (Start)
%F A157792 a(n) = a(n-1) + a(n-3) - a(n-4) for n > 12.
%F A157792 G.f.: x*(x^11 - x^9 - x^7 + x^6 - x^5 + x^4 - x^3 + x^2 + 1)/(x^4 - x^3 - x + 1). (End)
%e A157792 a(3) = 2 because all 9 points are visible from (1,1) and (1,2).
%e A157792 a(5) = 3 because all 25 points are visible from (1,1), (1,2), and (1,4).
%e A157792 a(7) = 4 because all 49 points are visible from (1,1), (1,2), (1,3), and (1,6).
%e A157792 a(12)= 5 because all 144 points are visible from (1,1), (1,3), (1,6), (1,8), and (1,11).
%t A157792 Join[{1}, Table[hidden=Table[{},{n^2}]; edgePts={}; Do[pt1=(c-1)*n+d; If[c==1, 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[n,k]; i=0; While[i<len, i++; s=Subsets[edgePts,{k},{i}][[1]]; If[Intersection@@hidden[[s]]=={}, done=True; Break[]]]]; k, {n,2,11}]]
%Y A157792 Cf. A157639, A157720, A157790, A157791.
%K A157792 hard,nonn
%O A157792 1,3
%A A157792 _T. D. Noe_, Mar 06 2009
%E A157792 More terms from _Lars Blomberg_, Nov 06 2014