A141255 -id:A141255 - cp's OEIS frontend

A331771 a(n) = Sum_{-n

0, 12, 56, 172, 400, 836, 1496, 2564, 4080, 6212, 8984, 12788, 17488, 23644, 31112, 40148, 50912, 64172, 79448, 97868, 118912, 143108, 170504, 202500, 238080, 278700, 323864, 374508, 430272, 493380, 561832, 638692, 722656, 814604, 914360, 1023428

Offset: 1

N. J. A. Sloane, Feb 08 2020

nonn

a(n) = 8*A332612(n)+4*n*(n-1)+4*(n-1)^2. Also adding 2 to the terms of the present sequence gives (essentially) A114146. - N. J. A. Sloane, Mar 14 2020

Koplowitz, Jack, Michael Lindenbaum, and A. Bruckstein. "The number of digital straight lines on an N* N grid." IEEE Transactions on Information Theory 36.1 (1990): 192-197. (See I(n).)

Seiichi Manyama, Table of n, a(n) for n = 1..1000
M. A. Alekseyev, M. Basova, and N. Yu. Zolotykh. On the minimal teaching sets of two-dimensional threshold functions. SIAM Journal on Discrete Mathematics 29:1 (2015), 157-165. doi:10.1137/140978090. See p. 158.
N. J. A. Sloane, Families of Essentially Identical Sequences, Mar 24 2021 (Includes this sequence)

When divided by 4 this becomes A115005, so this is a ninth sequence to add to the following list.
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.
Cf. A332612.

VR := proc(m,n,q) local a,i,j; a:=0;
for i from -m+1 to m-1 do for j from -n+1 to n-1 do
if gcd(i,j)=q then a:=a+(m-abs(i))*(n-abs(j)); fi; od: od: a; end;
[seq(VR(n,n,1),n=1..50)];

a[n_] := Sum[Boole[GCD[i, j] == 1] (n - Abs[i]) (n - Abs[j]), {i, -n + 1, n - 1}, {j, -n + 1, n - 1}];
Array[a, 36] (* Jean-François Alcover, Apr 19 2020 *)

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

a(n) = 4 * A115005(n).

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

A332351 Triangle read by rows: T(m,n) = Sum_{-m= n >= 1.

Original entry on oeis.org

0, 1, 6, 2, 13, 28, 3, 22, 49, 86, 4, 33, 74, 131, 200, 5, 46, 105, 188, 289, 418, 6, 61, 140, 251, 386, 559, 748, 7, 78, 181, 326, 503, 730, 979, 1282, 8, 97, 226, 409, 632, 919, 1234, 1617, 2040, 9, 118, 277, 502, 777, 1132, 1521, 1994, 2517, 3106, 10, 141, 332, 603, 934, 1361, 1828, 2397, 3026, 3735, 4492

Offset: 1

N. J. A. Sloane, Feb 10 2020

This is the triangle in A332350, halved.

This triangle is the lower half of the array defined in A115009.

			Triangle begins:
0,
1, 6,
2, 13, 28,
3, 22, 49, 86,
4, 33, 74, 131, 200,
5, 46, 105, 188, 289, 418,
6, 61, 140, 251, 386, 559, 748,
7, 78, 181, 326, 503, 730, 979, 1282,
8, 97, 226, 409, 632, 919, 1234, 1617, 2040,
9, 118, 277, 502, 777, 1132, 1521, 1994, 2517, 3106,
...

Jovisa Zunic, Note on the number of two-dimensional threshold functions, SIAM J. Discrete Math. Vol. 25 (2011), No. 3, pp. 1266-1268. See Equation (1.2).

Paolo Xausa, Table of n, a(n) for n = 1..11325 (rows 1..150 of the triangle, flattened)
M. A. Alekseyev, M. Basova, and N. Yu. Zolotykh. On the minimal teaching sets of two-dimensional threshold functions. SIAM Journal on Discrete Mathematics 29:1 (2015), 157-165. doi:10.1137/140978090. This sequence is f_1(m,n)/2.

The main diagonal is A141255, or A114043 - 1.
Cf. A115009, A332350, A332352.
This is the lower triangle of the array in A115009.

VR := proc(m,n,q) local a,i,j; a:=0;
for i from -m+1 to m-1 do for j from -n+1 to n-1 do
if gcd(i,j)=q then a:=a+(m-abs(i))*(n-abs(j)); fi; od: od: a; end;
for m from 1 to 12 do lprint(seq(VR(m,n,1)/2,n=1..m),); od:

A332351[m_,n_]:=Sum[If[CoprimeQ[i,j],2(m-i)(n-j),0],{i,m-1},{j,n-1}]+2m*n-m-n;Table[A332351[m,n],{m,15},{n,m}] (* Paolo Xausa, Oct 18 2023 *)

A333283 Triangle read by rows: T(m,n) (m >= n >= 1) = number of edges formed by drawing the line segments connecting any two of the (m+1) X (n+1) lattice points in an m X n grid of squares and extending them to the boundary of the grid.

Original entry on oeis.org

8, 28, 92, 80, 320, 1028, 178, 716, 2348, 5512, 372, 1604, 5332, 12676, 28552, 654, 2834, 9404, 22238, 49928, 87540, 1124, 5008, 16696, 39496, 88540, 156504, 279100, 1782, 7874, 26458, 62818, 141386, 251136, 447870

Offset: 1

Scott R. Shannon and N. J. A. Sloane, Mar 16 2020

If we only joined pairs of the 2(m+n) boundary points, we would get A331454. If we did not extend the lines to the boundary of the grid, we would get A333278. (One of the links below shows the difference between the three definitions in the case m=3, n=2.)

See A333282 for a large number of colored illustrations.

			Triangle begins:
8,
28, 92,
80, 320, 1028,
178, 716, 2348, 5512,
372, 1604, 5332, 12676, 28552,
654, 2834, 9404, 22238, 49928, 87540,
1124, 5008, 16696, 39496, 88540, 156504, 279100,
1782, 7874, 26458, 62818, 141386, 251136, 447870, ...
...
T(7,7) corrected Mar 19 2020

Seppo Mustonen, Statistical accuracy of geometric constructions, 2008.
Seppo Mustonen, Statistical accuracy of geometric constructions, 2008 [Local copy]
Seppo Mustonen, On lines and their intersection points in a rectangular grid of points, 2009
Seppo Mustonen, On lines and their intersection points in a rectangular grid of points, 2009 [Local copy]
Seppo Mustonen, On lines going through a given number of points in a rectangular grid of points, 2010
Seppo Mustonen, On lines going through a given number of points in a rectangular grid of points, 2010 [Local copy]
N. J. A. Sloane, Illustration of T(3,2) = 320. [Black lines correspond to A331454(3,2), black + red lines correspond to A333278(3,2), and black + red + blue lines to T(3,2)]
N. J. A. Sloane, Illustration of T(3,3) = 1028 [Black lines correspond to A288187(3,3), and black + red lines to T(3,3)]

Cf. A288187, A331452, A333278, A331454, A333282 (regions), A333284 (vertices). Column 1 is A331757.

More terms and corrections from Scott R. Shannon, Mar 21 2020

A332612 a(n) = Sum_{ i=2..n-1, j=1..i-1, gcd(i,j)=1 } (n-i)*(n-j).

Original entry on oeis.org

0, 0, 2, 11, 32, 77, 148, 268, 442, 691, 1018, 1472, 2036, 2780, 3686, 4786, 6100, 7724, 9598, 11863, 14454, 17437, 20818, 24772, 29172, 34200, 39794, 46071, 52986, 60817, 69314, 78860, 89292, 100720, 113122, 126686, 141244, 157294, 174566, 193228, 213172, 234954, 258058, 283189, 309946, 338473, 368782, 401516, 436040

Offset: 1

Scott R. Shannon and N. J. A. Sloane, Mar 14 2020

nonn

Related to the number of linear dichotomies on a square grid.

A331771(n) = 8*a(n) + 4*n*(n-1) + 4*(n-1)^2.

Seiichi Manyama, Table of n, a(n) for n = 1..1000
Jack Koplowitz, Michael Lindenbaum, and A. Bruckstein, The number of digital straight lines on an NxN grid, IEEE Transactions on Information Theory 36.1 (1990): 192-197. (See I_1.)

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. The present sequence and A331771 could be added to this list.

I1 := proc(n) local a, i, j; a:=0;
for i from 2 to n-1 do for j from 1 to i-1 do
if igcd(i,j)=1 then a := a+(n-i)*(n-j); fi; od; od; a; end;
[seq(I1(n),n=1..40)];

a(n) = sum(i=2, n-1, sum(j=1, i-1, if (gcd(i,j)==1, (n-i)*(n-j)))); \\ Michel Marcus, Mar 14 2020

from sympy import totient
def A332612(n): return sum(totient(i)*(n-i)*(2*n-i) for i in range(2,n))//2 # Chai Wah Wu, Aug 17 2021

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

A333284 Triangle read by rows: T(m,n) (m >= n >= 1) = number of vertices formed by drawing the line segments connecting any two of the (m+1) X (n+1) lattice points in an m X n grid of squares and extending them to the boundary of the grid.

Original entry on oeis.org

5, 13, 37, 35, 129, 405, 75, 289, 933, 2225, 159, 663, 2155, 5157, 11641, 275, 1163, 3793, 9051, 20341, 35677, 477, 2069, 6771, 16129, 36173, 63987, 114409, 755, 3251, 10727, 25635, 57759, 102845, 183961

Offset: 1

Scott R. Shannon and N. J. A. Sloane, Mar 16 2020

If we only joined pairs of the 2(m+n) boundary points, we would get A331453. If we did not extend the lines to the boundary of the grid, we would get A288180. (One of the links below shows the difference between the three definitions in the case m=3, n=2.)

See A333282 for a large number of colored illustrations.

			Triangle begins:
5,
13, 37,
35, 129, 405,
75, 289, 933, 2225,
159, 663, 2155, 5157, 11641,
275, 1163, 3793, 9051, 20341, 35677,
477, 2069, 6771, 16129, 36173, 63987, 114409,
755, 3251, 10727, 25635, 57759, 102845, 183961, ...
...
T(7,7) corrected Mar 19 2020

Lars Blomberg, Scott R. Shannon, N. J. A. Sloane, Graphical Enumeration and Stained Glass Windows, 1: Rectangular Grids, (2021). Also arXiv:2009.07918.
Seppo Mustonen, Statistical accuracy of geometric constructions, 2008.
Seppo Mustonen, Statistical accuracy of geometric constructions, 2008 [Local copy]
Seppo Mustonen, On lines and their intersection points in a rectangular grid of points, 2009
Seppo Mustonen, On lines and their intersection points in a rectangular grid of points, 2009 [Local copy]
Seppo Mustonen, On lines going through a given number of points in a rectangular grid of points, 2010
Seppo Mustonen, On lines going through a given number of points in a rectangular grid of points, 2010 [Local copy]
N. J. A. Sloane, Illustration of T(3,2) = 129. [Black lines correspond to A331453(3,2), black + red lines correspond to A288180(3,2), and black + red + blue lines to T(3,2)]
N. J. A. Sloane, Illustration of T(3,3) = 405 [Black lines correspond to A288180(3,3), and black + red lines to T(3,3)]

Cf. A288187, A331452, A288180, A331453, A333282 (regions), A333283 (edges). Column 1 is A331755. The main diagonal is A333285.

More terms and corrections from Scott R. Shannon, Mar 21 2020

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

A177720 Number of line segments connecting exactly 4 points in an n x n grid of points.

Original entry on oeis.org

0, 0, 0, 10, 28, 54, 104, 170, 252, 394, 568, 774, 1068, 1410, 1800, 2374, 3028, 3762, 4656, 5646, 6732, 8190, 9792, 11538, 13636, 15910, 18360, 21334, 24532, 27954, 31856, 36014, 40428, 45798, 51504, 57546, 64228, 71278, 78696, 87466, 96700

Offset: 1

Seppo Mustonen, May 13 2010

nonn

a(n) is also the number of pairs of points visible to each other exactly through 2 points in an n x n grid of points.

S. Mustonen, On lines going through a given number of points in a rectangular grid of points
Seppo Mustonen, On lines going through a given number of points in a rectangular grid of points [Local copy]

j=3;
a[n_]:=a[n]=If[n<=j,0,2*a1[n]-a[n-1]+R1[n]]
a1[n_]:=a1[n]=If[n<=j,0,2*a[n-1]-a1[n-1]+R2[n]]
R1[n_]:=R1[n]=If[n<=j,0,R1[n-1]+4*S[n]]
R2[n_]:=(n-1)*S[n]
S[n_]:=If[Mod[n-1,j]==0,EulerPhi[(n-1)/j],0]
Table[a[n],{n,1,50}]

See Mathematica code.

A355902 Start with a 2 X n array of squares, join every vertex on top edge to every vertex on bottom edge; a(n) = one-half the number of cells.

Original entry on oeis.org

0, 3, 10, 26, 56, 112, 196, 331, 522, 790, 1138, 1615, 2204, 2975, 3910, 5041, 6388, 8047, 9958, 12262, 14894, 17920, 21346, 25347, 29796, 34875, 40522, 46854, 53826, 61716, 70274, 79883, 90380, 101875, 114346, 127981, 142612, 158737, 176086, 194827, 214852, 236717, 259906, 285124, 311970, 340588, 370990, 403819, 438440, 475556

Offset: 0

Scott R. Shannon and N. J. A. Sloane, Sep 05 2022

nonn

Note that this figure can be obtained by drawing an "equatorial" line through the middle of the strip of n adjacent rectangles in A306302. This cuts each of the 2n "equatorial" cells in A306302 in two. It follows that 2*a(n) = A306302(n) + 2*n, i.e. that a(n) = A306302(n)/2 + n. Note that there is an explicit formula for A306302(n) in terms of n. - Scott R. Shannon, Sep 06 2022.

This means the present sequence is one more member of the large class of sequences which are essentially the same as A115004 (see Cross-References). - N. J. A. Sloane, Sep 06 2022

Scott R. Shannon, Image for a(4) = 56. Note in this and other images the entire 2xn array is shown so the number of cells is twice a(n).
Scott R. Shannon, Image for a(6) = 196.
Scott R. Shannon, Image for a(10) = 1138.
Scott R. Shannon, Image for a(15) = 5041.
N. J. A. Sloane, Illustration for a(2) = 10.
N. J. A. Sloane, Illustration for a(3) = 26.

Cf. A356790, A306302, A355798, A290131, A331452.

The following nine 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; A355902(n) = n + A306302(n)/2. - N. J. A. Sloane, Sep 06 2022

a(n) = A356790(2,n+2)/2 - 2.

A333285 The main diagonal of the triangular array A333284.

Original entry on oeis.org

5, 37, 405, 2225, 11641, 35677, 114409, 295701, 718469, 1475709, 3093025, 5771929, 10895273, 18785841, 31414269, 50274501, 81288641, 124066161, 190860537, 282399889, 411505049, 580614301, 824814797, 1138709849, 1570665877, 2115178249, 2833746309, 3732420861, 4937226173

Offset: 1

Scott R. Shannon and N. J. A. Sloane, Mar 16 2020

nonn

See A333282, A333283, and A333284 for further information, illustrations, etc.

Lars Blomberg, Scott R. Shannon, N. J. A. Sloane, Graphical Enumeration and Stained Glass Windows, 1: Rectangular Grids, (2021). Also arXiv:2009.07918.
Seppo Mustonen, Statistical accuracy of geometric constructions, September 02, 2008.
Seppo Mustonen, Statistical accuracy of geometric constructions, 2008 [Local copy]
Seppo Mustonen, On lines and their intersection points in a rectangular grid of points, 2009
Seppo Mustonen, On lines and their intersection points in a rectangular grid of points, 2009 [Local copy]
Seppo Mustonen, On lines going through a given number of points in a rectangular grid of points, 2010
Seppo Mustonen, On lines going through a given number of points in a rectangular grid of points, 2010 [Local copy]

Cf. A333282, A333283, A333284.

cp's OEIS Frontend

A331771 a(n) = Sum_{-n

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

A332351 Triangle read by rows: T(m,n) = Sum_{-m= n >= 1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

A333283 Triangle read by rows: T(m,n) (m >= n >= 1) = number of edges formed by drawing the line segments connecting any two of the (m+1) X (n+1) lattice points in an m X n grid of squares and extending them to the boundary of the grid.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A332612 a(n) = Sum_{ i=2..n-1, j=1..i-1, gcd(i,j)=1 } (n-i)*(n-j).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

PARI

Python

Formula

A333284 Triangle read by rows: T(m,n) (m >= n >= 1) = number of vertices formed by drawing the line segments connecting any two of the (m+1) X (n+1) lattice points in an m X n grid of squares and extending them to the boundary of the grid.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

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

A177720 Number of line segments connecting exactly 4 points in an n x n grid of points.

Views

Author

Keywords

Comments