Search: id:A157639
Results 1-1 of 1 results found.

%I A157639
%S A157639 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,
%T A157639 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,
%U A157639 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
%N A157639 Least number of lattice points from which every point of a square n x 
               n lattice is visible.
%C A157639 Adhikari and Granville give bounds on the size of a(n).
%C A157639 Contribution from Jon E. Schoenfield (jonscho(AT)hiwaay.net), Aug 03 
               2009: (Start)
%C A157639 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.
%C A157639 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.
%C A157639 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.
%C A157639 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 
               by k-column subset of the m-row by 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.
%C A157639 Per exhaustive search, no 4-viewpoint solution exists for n=133, so a(133)=5.
%C A157639 In summary: a(1..3)=1, a(4..5)=2, a(6..23)=3, a(24..132)=4, a(133)=5. 
               (End)
%H A157639 Sukumar Das Adhikari and Andrew Granville, <a href="http://www.dms.umontreal.ca/
               ~andrew/PDF/VisibleLatticePts.pdf">Visibility in the Plane</a>
%H A157639 Eric Weisstein, <a href="http://mathworld.wolfram.com/VisiblePoint.html">
               MathWorld: Visible Point</a>
%e A157639 a(3) = 1 because all 9 points are visible from the central (2,2) point.
%e A157639 a(4) = 2 because all 16 points are visible from (1,2) or (2,1).
%e A157639 a(6) = 3 because all 36 points are visible from (1,1), (1,2), or (2,1).
%e A157639 a(24)= 4 because all 576 points are visible from (1,1), (1,2), (1,3), 
               or (2,24).
%t A157639 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}]
%Y A157639 A141224
%Y A157639 Sequence in context: A106482 A122462 A165024 this_sequence A010096 A063510 
               A156878
%Y A157639 Adjacent sequences: A157636 A157637 A157638 this_sequence A157640 A157641 
               A157642
%K A157639 hard,nice,nonn
%O A157639 1,4
%A A157639 T. D. Noe (noe(AT)sspectra.com), Mar 03 2009
%E A157639 Terms after a(24) from Jon E. Schoenfield (jonscho(AT)hiwaay.net), Aug 
               03 2009
%E A157639 Corrected/updated comment to include 4-viewpoint solution showing a(n)<=4 
               for n=78..132 Jon E. Schoenfield (jonscho(AT)hiwaay.net), Aug 09 
               2009
%E A157639 Incorporated result that a(133)=5 Jon E. Schoenfield (jonscho(AT)hiwaay.net), 
               Sep 02 2009

Search completed in 0.001 seconds