login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A157639 Least number of lattice points from which every point of a square n X n lattice is visible. 5
1, 1, 1, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,4

COMMENTS

Adhikari and Granville give bounds on the size of a(n).

From Jon E. Schoenfield, Aug 03 2009, Aug 09 2009, Sep 02 2009: (Start)

Consider an arbitrarily large lattice. Define S1 as the square having both X and Y in the closed interval [1,3]. From a single viewpoint at (2,2), every lattice point on or inside S1 is visible. S1 (including its edges) covers 3 rows X 3 columns of lattice points, so a(3)=1. Also, since an n-row X n-column subset of S1 that includes the one viewpoint can be selected for n=1 and for n=2, this 1-viewpoint example is sufficient to show that a(n)=1 for n = 1..3.

Define S2 as the square having both X and Y in [1,5]. Every lattice point in S2 is visible from at least one of the two viewpoints (3,1) and (3,4). S2 covers 5 rows X 5 columns of points, so a(5) <= 2. Since a 4-row X 4-column subset of S2 that includes the two viewpoints can also be selected, a(4) <= 2. Since no 1-viewpoint solution exists for n > 3, we have a(n)=2 for n=4 and n=5.

Proceeding similarly, every lattice point where X and Y are both in [1,23] is visible from at least one of the three viewpoints (14,14), (15,14), and (14,15), so a(n) <= 3 for n = 2..23. Since no 2-viewpoint solution exists for n > 5, we have a(n)=3 for n = 6..23.

Together, the three 4-viewpoint solutions {(20,20), (21,20), (20,21), (21,21)}, {(43,51), (72,65), (58,80), (57,66)}, and {(28,34), (105,105), (34,99), (99,40)} are sufficient to show that a(n) <= 4 for n = 24..132: in these solutions, every lattice point where X and Y are both in [1,m], where m = 40, 128, and 132, respectively, is visible from at least one viewpoint, and all four viewpoints would fit in a k-row X k-column subset of the m-row X m-column square, for k as small as 2, 30, and 78, respectively. Thus these three solutions demonstrate that a(n) <= 4 for the overlapping ranges n = 2..40, n = 30..128, and n = 78..132, respectively. Since (per an exhaustive search) no 3-viewpoint solution exists for n = 24..132, we have a(n)=4 for n = 24..132.

Per exhaustive search, no 4-viewpoint solution exists for n=133, so a(133)=5.

In summary: a(1..3)=1, a(4..5)=2, a(6..23)=3, a(24..132)=4, a(133)=5. (End)

LINKS

Table of n, a(n) for n=1..105.

Sukumar Das Adhikari and Andrew Granville, Visibility in the Plane

Eric Weisstein's World of Mathematics, Visible Point

EXAMPLE

a(3) = 1 because all 9 points are visible from the central (2,2) point.

a(4) = 2 because all 16 points are visible from (1,2) or (2,1).

a(6) = 3 because all 36 points are visible from (1,1), (1,2), or (2,1).

a(24)= 4 because all 576 points are visible from (1,1), (1,2), (1,3), or (2,24).

MATHEMATICA

Table[sees=Table[{}, {n^2}]; Do[pt1=(c-1)*n+d; lst={}; Do[pt2=(a-1)*n+b; If[GCD[c-a, d-b]<2, AppendTo[lst, pt2]], {a, n}, {b, n}]; sees[[pt1]]=lst, {c, n}, {d, n}]; done=False; k=0; While[ !done, k++; len=Binomial[n^2, k]; i=0; While[i<len, i++; s=Subsets[Range[n^2], {k}, {i}][[1]]; If[Length[Union@@sees[[s]]]==n^2, done=True; Break[]]]]; k, {n, 10}]

CROSSREFS

Cf. A141224.

Sequence in context: A300402 A326166 A211020 * A010096 A230864 A063510

Adjacent sequences:  A157636 A157637 A157638 * A157640 A157641 A157642

KEYWORD

hard,nice,nonn

AUTHOR

T. D. Noe, Mar 03 2009

EXTENSIONS

Terms after a(24) from Jon E. Schoenfield, Aug 03 2009

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 29 10:41 EDT 2020. Contains 334699 sequences. (Running on oeis4.)