A141224 -id:A141224 - cp's OEIS frontend

A141255 Total number of line segments between points visible to each other in a square n X n lattice.

0, 6, 28, 86, 200, 418, 748, 1282, 2040, 3106, 4492, 6394, 8744, 11822, 15556, 20074, 25456, 32086, 39724, 48934, 59456, 71554, 85252, 101250, 119040, 139350, 161932, 187254, 215136, 246690, 280916, 319346, 361328, 407302, 457180, 511714, 570232

Offset: 1

T. D. Noe, Jun 17 2008

nonn

A line segment joins points (a,b) and (c,d) if the points are distinct and gcd(c-a,d-b)=1.

			The 2 x 2 square lattice has a total of 6 line segments: 2 vertical, 2 horizontal and 2 diagonal.

D. M. Acketa, J. D. Zunic: On the number of linear partitions of the (m,n)-grid. Inform. Process. Lett., 38 (3) (1991), 163-168. See Table A.1.
Jovisa Zunic, Note on the number of two-dimensional threshold functions, SIAM J. Discrete Math. Vol. 25 (2011), No. 3, pp. 1266-1268. See Eq. (1.2).

Chai Wah Wu, Table of n, a(n) for n = 1..10000
Seppo Mustonen, On lines going through a given number of points in a rectangular grid of points [From _Seppo Mustonen_, May 13 2010]
Seppo Mustonen, On lines going through a given number of points in a rectangular grid of points [Local copy]
N. J. A. Sloane, Families of Essentially Identical Sequences, Mar 24 2021 (Includes this sequence)

Cf. A141224.

The following eight sequences are all essentially the same. The simplest is A115004(n), which we denote by z(n). Then A088658(n) = 4*z(n-1); A114043(n) = 2*z(n-1)+2*n^2-2*n+1; A114146(n) = 2*A114043(n); A115005(n) = z(n-1)+n*(n-1); A141255(n) = 2*z(n-1)+2*n*(n-1); A290131(n) = z(n-1)+(n-1)^2; A306302(n) = z(n)+n^2+2*n. - N. J. A. Sloane, Feb 04 2020

Table[cnt=0; Do[If[GCD[c-a,d-b]<2, cnt++ ], {a,n}, {b,n}, {c,n}, {d,n}]; (cnt-n^2)/2, {n,20}]
(* This recursive code is much more efficient. *)
a[n_]:=a[n]=If[n<=1,0,2*a1[n]-a[n-1]+R1[n]]
a1[n_]:=a1[n]=If[n<=1,0,2*a[n-1]-a1[n-1]+R2[n]]
R1[n_]:=R1[n]=If[n<=1,0,R1[n-1]+4*EulerPhi[n-1]]
R2[n_]:=(n-1)*EulerPhi[n-1]
Table[a[n],{n,1,37}]
(* Seppo Mustonen, May 13 2010 *)
a[n_]:=2 Sum[(n-i) (n-j) Boole[CoprimeQ[i,j]], {i,1,n-1}, {j,1,n-1}] + 2 n^2 - 2 n; Array[a, 40] (* Vincenzo Librandi, Feb 05 2020 *)

from sympy import totient
def A141255(n): return 2*(n-1)*(2*n-1) + 2*sum(totient(i)*(n-i)*(2*n-i) for i in range(2,n)) # Chai Wah Wu, Aug 16 2021

a(n) = A114043(n) - 1.

a(n) = 2*(n-1)*(2n-1) + 2*Sum_{i=2..n-1} (n-i)*(2n-i)*phi(i). - Chai Wah Wu, Aug 16 2021

A141225 Number of points having maximal visibility in a square n x n lattice.

Original entry on oeis.org

1, 4, 1, 4, 8, 16, 8, 12, 16, 36, 9, 60, 16, 16, 8, 12, 12, 12, 12, 36, 16, 16, 25, 4, 16, 8, 5, 12, 24, 64, 12, 8, 4, 4, 25, 16, 4, 8, 1, 20, 16, 4, 20, 12, 4, 4, 9, 8, 4, 4, 4, 4, 12, 4, 4, 4, 4, 12, 9, 4, 8, 4, 8, 12, 8, 4, 4, 8, 4, 16, 12, 20, 4, 8, 4, 4, 16, 4, 4, 4, 4, 4, 4, 4, 4, 4, 8, 4, 4

Offset: 1

T. D. Noe, Jun 15 2008

nonn

Sequence A141224 gives the maximum number of points visible from some point. By symmetry, when a(n) is odd, the central point in the lattice can see the maximal number of points. When a(n)=1, the central point is the only such point. See A141226 for the n x n lattices that have such a central point.

T. D. Noe, Table of n, a(n) for n=1..1000

Table[mx=0; pts=0; Do[cnt=0; Do[If[GCD[c-a,d-b]<2, cnt++ ], {a,n}, {b,n}]; If[cnt>mx, mx=cnt; pts=1, If[cnt==mx, pts++ ]], {c,n}, {d,n}]; pts, {n,20}]

A157639 Least number of lattice points from which every point of a square n X n lattice is visible.

Original entry on oeis.org

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

Offset: 1

T. D. Noe, Mar 03 2009

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)

			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).

Sukumar Das Adhikari and Andrew Granville, Visibility in the Plane
Eric Weisstein's World of Mathematics, Visible Point

Cf. A141224.

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

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

A372217 a(n) is the number of distinct triangles whose sides do not pass through a grid point and whose vertices are three points of an n X n grid.

Original entry on oeis.org

0, 1, 3, 8, 14, 36, 48, 100, 146, 232, 294, 502, 595, 938, 1143, 1433, 1741, 2512, 2826, 3911, 4458, 5319, 6067, 7976, 8728, 10750, 12076, 14194, 15671, 19510, 20669, 25349, 28115, 31716, 34697, 39467, 41894, 49766, 54046, 59948, 63951, 74818, 78216, 90773, 97220

Offset: 0

Felix Huber, Apr 28 2024

nonn

			See the linked illustration for the terms a(1) = 1, a(2) = 3, a(3) = 8, a(4) = 14, a(5) = 36 and a(6) = 48.

Felix Huber, Illustration of the terms a(1) to a(6).

Cf. A115004, A141224, A141255, A320540, A320541, A320544, A372218.

S372217:=proc(n);
  local s,x,u,v;
  s:=0;
  if n=1 then return 1 fi;
  for x to n do
    if gcd(x,n)=1 then
      for u from x to n do
        for v from 0 to n do
          if gcd(u,v)=1 and gcd(u-x,n-v)=1 then
            if u=x then s:=s+1;
            fi;
          fi;
        od;
      od;
    fi;
  od;
  return s;
end proc;
A372217:=proc(n)
  local i,a;
  a:=0;
  for i from 0 to n do
    a:=a+S372217(i);
  od;
  return a;
end proc;
seq(A372217(n),n=0..44);

A372218 a(n) is the number of ways to select three distinct points of an n X n grid forming a triangle whose sides do not pass through a grid point.

Original entry on oeis.org

0, 4, 36, 184, 592, 1828, 4164, 9360, 18592, 34948, 59636, 102096, 161496, 255700, 385292, 562336, 796344, 1131996, 1552780, 2133368, 2855632, 3765492, 4876444, 6328104, 8049744, 10203820, 12766508, 15870744, 19496392, 23984444, 29090340, 35318968, 42535496, 50936036

Offset: 0

Felix Huber, Apr 28 2024

nonn

a(n) is 1/6 of the number of ways to select three points (x,y), (u,v), (p,q) with gcd(x-u,y-v) = gcd(u-p,v-q) = gcd(p-x,q-y) = 1 and 0 <= x, y, u, v, p, q <= n in an n X n grid.

			See the linked illustration: a(2) = 36 because there are 36 ways to select three distinct points in a square grid with side length n that satisfy the condition.

Felix Huber, Illustration of a(2)

Cf. A115004, A141224, A141255, A320540, A320541, A320544, A372217.

A372218:=proc(n)
  local x,y,u,v,p,q,a;
  a:=0;
  for x from 0 to n do
    for y from 0 to n do
      for u from 0 to n do
        for v from 0 to n do
          if gcd(x-u,y-v)=1 then
            for p from 0 to n do
              for q from 0 to n do
                if gcd(x-p,y-q)=1 and gcd(p-u,q-v)=1 then a:=a+1 fi;
              od;
            od;
          fi;
        od;
      od;
    od;
  od;
  a:=a/6;
  return a;
end proc;
seq(A372218(n),n=0..33);

A141247 Minimum number of points visible from a point in a square n X n lattice.

Original entry on oeis.org

1, 4, 6, 10, 14, 22, 26, 38, 46, 58, 66, 86, 94, 118, 130, 146, 162, 194, 206, 241, 257, 282, 302, 346, 362, 401, 426, 462, 486, 542, 558, 609, 641, 690, 722, 770, 794, 861, 899, 950, 982, 1062, 1086, 1157, 1201, 1258, 1302, 1393, 1425, 1501, 1546, 1613

Offset: 1

T. D. Noe, Jun 17 2008

nonn

Two points (a,b) and (c,d) are visible to each other when gcd(c-a,d-b)=1. Sequence A141248 gives the number of lattice points that have minimal visibility.

T. D. Noe, Table of n, a(n) for n=1..1000
Eric Weisstein, MathWorld: Visible Point

Cf. A141224.

Table[mn=n^2+1; Do[cnt=0; Do[If[GCD[c-a,d-b]<2, cnt++ ], {a,n}, {b,n}]; If[cnt

The minimum number of visible points is slightly less than c*n^2, with c = 6/pi^2.

A141227 Maximum number of points visible from some point in a cubic n x n x n lattice.

Original entry on oeis.org

1, 8, 27, 57, 111, 183, 303, 435, 633, 843, 1155, 1443, 1893, 2313, 2895, 3447, 4215, 4875, 5865, 6723, 7887, 8943, 10371, 11553, 13293, 14745, 16707, 18411, 20703, 22485, 25257, 27459, 30423, 32931, 36291, 38889, 42837, 45950, 50115, 53523

Offset: 1

T. D. Noe, Jun 15 2008

nonn

Two points (a,b,c) and (d,e,f) are visible to each other when gcd(d-a,e-b,f-c)=1. Sequence A141228 gives the number of lattice points that have maximal visibility.

Eric Weisstein, MathWorld: Visible Point

Cf. A141224.

Table[mx=0; Do[cnt=0; Do[If[GCD[d-a,e-b,f-c]<2, cnt++ ], {a,n}, {b,n}, {c,n}]; If[cnt>mx, mx=cnt], {d,n}, {e,n}, {f,n}]; mx, {n,10}]

The maximum number of visible points is slightly more than c*n^3, with c = 1/zeta(3) = 0.831907... (A088453).

cp's OEIS Frontend

A141255 Total number of line segments between points visible to each other in a square n X n lattice.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Python

Formula

A141225 Number of points having maximal visibility in a square n x n lattice.

Views

Author

Keywords

Comments

Links

Programs

Mathematica

A157639 Least number of lattice points from which every point of a square n X n lattice is visible.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A372217 a(n) is the number of distinct triangles whose sides do not pass through a grid point and whose vertices are three points of an n X n grid.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

A372218 a(n) is the number of ways to select three distinct points of an n X n grid forming a triangle whose sides do not pass through a grid point.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

A141247 Minimum number of points visible from a point in a square n X n lattice.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A141227 Maximum number of points visible from some point in a cubic n x n x n lattice.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula