|
| |
|
|
A157792
|
|
Least number of lattice points on one side from which every point of a square n X n lattice is visible.
|
|
2
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,3
|
|
|
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.
|
|
|
LINKS
|
|
|
|
FORMULA
|
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)
|
|
|
EXAMPLE
|
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).
|
|
|
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<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
|
| |
|
|
