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

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, 11, 12, 12, 12, 13, 13, 13, 14, 14, 14, 15, 15, 15, 16, 16, 16, 17, 17, 17, 18, 18, 18, 19, 19, 19, 20, 20, 20, 21, 21, 21, 22, 22, 22, 23, 23, 23, 24, 24, 24, 25

Offset: 1

Author

T. D. Noe, Mar 06 2009

Keywords

• hard
• nonn

Comments

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.

Examples

			a(3) = 2 because all 9 points are visible from (1,1) and (1,2).
a(5) = 3 because all 25 points are visible from (1,1), (1,2), and (1,4).
a(7) = 4 because all 49 points are visible from (1,1), (1,2), (1,3), and (1,6).
a(12)= 5 because all 144 points are visible from (1,1), (1,3), (1,6), (1,8), and (1,11).
		

Links

• Eric Weisstein's World of Mathematics, Visible Point

Crossrefs

Cf. A157639, A157720, A157790, A157791.

Programs

Mathematica

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
				

Formula

Conjectures from Chai Wah Wu, Aug 05 2022: (Start)

a(n) = a(n-1) + a(n-3) - a(n-4) for n > 12.

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)

Extensions

More terms from Lars Blomberg, Nov 06 2014