A320541 -id:A320541 - cp's OEIS frontend

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

1, 8, 31, 80, 179, 332, 585, 948, 1463, 2136, 3065, 4216, 5729, 7568, 9797, 12456, 15737, 19520, 24087, 29308, 35315, 42120, 50073, 58920, 69025, 80264, 92871, 106756, 122475, 139528, 158681, 179608, 202529, 227400, 254597, 283784, 315957, 350576, 387977

Offset: 1

N. J. A. Sloane, Feb 23 2006

Also (1/4) * number of ways to select 3 distinct points forming a triangle of unsigned area = 1/2 from a square of grid points with side length n. Diagonal of triangle A320541. - Hugo Pfoertner, Oct 22 2018
From Chai Wah Wu, Aug 18 2021: (Start)
Theorem: a(n) = n^2 + Sum_{i=2..n} (n+1-i)*(2*n+2-i)*phi(i).
Proof: Since gcd(n,n) = 1 if and only if n = 1, Sum_{i=1..n, j=1..n, gcd(i,j)=1} (n+1-i)*(n+1-j) = n^2 + Sum_{i=1..n, j=1..n, gcd(i,j)=1, (i,j) <> (1,1)} (n+1-i)*(n+1-j)
= n^2 + Sum_{i=2..n, j=1..i, gcd(i,j)=1} (n+1-i)*(n+1-j) + Sum_{j=2..n, i=1..j, gcd(i,j)=1} (n+1-i)*(n+1-j) = n^2 + 2*Sum_{i=2..n, j=1..i, gcd(i,j)=1} (n+1-i)*(n+1-j), i.e., the diagonal is not double-counted.
This is equal to n^2 + 2*Sum_{i=2..n, j is a totative of i} (n+1-i)*(n+1-j). Since Sum_{j is a totative of i} 1 = phi(i) and for i > 1, Sum_{j is a totative of i} j = i*phi(i)/2, the conclusion follows.
Similar argument holds for corresponding formulas for A088658, A114043, A114146, A115005, etc.
(End)

Ray Chandler, Table of n, a(n) for n = 1..1000
M. Griffiths, Counting the regions in a regular drawing of K_{n,n}, J. Int. Seq. 13 (2010) # 10.8.5.
S. Legendre, The Number of Crossings in a Regular Drawing of the Complete Bipartite Graph, JIS 12 (2009) 09.5.5.
R. J. Mathar, Graphical representation among sequences closely related to this one (cf. N. J. A. Sloane, "Families of Essentially Identical Sequences").
N. J. A. Sloane, Families of Essentially Identical Sequences, Mar 24 2021. (Includes this sequence)
N. J. A. Sloane (in collaboration with Scott R. Shannon), Art and Sequences, Slides of guest lecture in Math 640, Rutgers Univ., Feb 8, 2020. Mentions this sequence.

Cf. A320540, A320541, A320544.
The following eight sequences are all essentially the same. The simplest is the present sequence, 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
Main diagonal of array in A114999.

A115004 := proc(n)
    local a,b,r ;
    r := 0 ;
    for a from 1 to n do
    for b from 1 to n do
        if igcd(a,b) = 1 then
            r := r+(n+1-a)*(n+1-b);
        end if;
    end do:
    end do:
    r ;
end proc:
seq(A115004(n),n=1..30); # R. J. Mathar, Jul 20 2017

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

a(n) = n^2 + sum(i=2, n, (n+1-i)*(2*n+2-i)*eulerphi(i)); \\ Michel Marcus, May 08 2024

from math import gcd
def a115004(n):
    r=0
    for a in range(1, n + 1):
        for b in range(1, n + 1):
            if gcd(a, b)==1:
                r+=(n + 1 - a)*(n + 1 - b)
    return r
print([a115004(n) for n in range(1, 51)]) # Indranil Ghosh, Jul 21 2017

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

a(n) = Sum_{i=1..n, j=1..n, gcd(i,j)=1} (n+1-i)*(n+1-j).
As n -> oo, a(n) ~ (3/2)*n^4/Pi^2. This follows from Max Alekseyev's formula in A114043. - N. J. A. Sloane, Jul 03 2020
a(n) = n^2 + Sum_{i=2..n} (n+1-i)*(2n+2-i)*phi(i). - Chai Wah Wu, Aug 15 2021

A114999 Array read by antidiagonals: T(m,n) = Sum_{i=1..m, j=1..n, gcd(i,j)=1} (m+1-i)*(n+1-j), m>=1, n>=1.

Original entry on oeis.org

1, 3, 3, 6, 8, 6, 10, 16, 16, 10, 15, 26, 31, 26, 15, 21, 39, 50, 50, 39, 21, 28, 54, 75, 80, 75, 54, 28, 36, 72, 103, 120, 120, 103, 72, 36, 45, 92, 137, 164, 179, 164, 137, 92, 45, 55, 115, 175, 218, 244, 244, 218, 175, 115, 55, 66, 140, 218, 278, 324, 332, 324, 278, 218, 140

Offset: 1

N. J. A. Sloane, Feb 23 2006

The corresponding triangle is A320541, counting (1/4) * number of ways to select 3 distinct points forming a triangle of unsigned area = 1/2 from a rectangle of grid points with side lengths j and k, written as triangle T(j,k), j<=k. - Hugo Pfoertner, Oct 22 2018

			The top left corner of the array is:
[1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78]
[3, 8, 16, 26, 39, 54, 72, 92, 115, 140, 168, 198]
[6, 16, 31, 50, 75, 103, 137, 175, 218, 265, 318, 374]
[10, 26, 50, 80, 120, 164, 218, 278, 346, 420, 504, 592]
[15, 39, 75, 120, 179, 244, 324, 413, 514, 623, 747, 877]
[21, 54, 103, 164, 244, 332, 441, 562, 699, 846, 1014, 1190]
[28, 72, 137, 218, 324, 441, 585, 745, 926, 1120, 1342, 1575]
[36, 92, 175, 278, 413, 562, 745, 948, 1178, 1424, 1706, 2002]
[45, 115, 218, 346, 514, 699, 926, 1178, 1463, 1768, 2118, 2485]
[55, 140, 265, 420, 623, 846, 1120, 1424, 1768, 2136, 2559, 3002]
[66, 168, 318, 504, 747, 1014, 1342, 1706, 2118, 2559, 3065, 3595]
[78, 198, 374, 592, 877, 1190, 1575, 2002, 2485, 3002, 3595, 4216]
...

Max A. Alekseyev. On the number of two-dimensional threshold functions. SIAM J. Disc. Math. 24(4), 2010, pp. 1617-1631. doi:10.1137/090750184

Cf. A114043, A115004 (main diagonal), A115005, A115006, A115007, A320541.

T:=proc(m,n) local t1,i,j; t1:=0; for i from 1 to m do for j from 1 to n do if gcd(i,j)=1 then t1:=t1+(m+1-i)*(n+1-j); fi; od; od; t1; end;

T[m_, n_] := Module[{t1, i, j}, t1 = 0; For[i = 1, i <= m, i++, For[j = 1, j <= n, j++, If[GCD[i, j] == 1 , t1 = t1 + (m+1-i)*(n+1-j)]]]; t1]; Table[T[m-n+1, n], {m, 1, 11}, {n, 1, m}] // Flatten (* Jean-François Alcover, Jan 07 2014, translated from Maple *)

A331762 Triangle read by rows: T(n,k) (1 <= k <= n) = Sum_{i=1..n, j=1..k, gcd(i,j)=2} (n+1-i)*(k+1-j).

Original entry on oeis.org

0, 0, 1, 0, 2, 4, 0, 4, 8, 15, 0, 6, 12, 22, 32, 0, 9, 18, 33, 48, 71, 0, 12, 24, 44, 64, 94, 124, 0, 16, 32, 58, 84, 123, 162, 211, 0, 20, 40, 72, 104, 152, 200, 260, 320, 0, 25, 50, 90, 130, 190, 250, 325, 400, 499

Offset: 1

N. J. A. Sloane, Feb 04 2020

			Triangle begins:
  0;
  0,  1;
  0,  2,  4;
  0,  4,  8,  15;
  0,  6, 12,  22,  32;
  0,  9, 18,  33,  48,  71;
  0, 12, 24,  44,  64,  94, 124;
  0, 16, 32,  58,  84, 123, 162, 211;
  0, 20, 40,  72, 104, 152, 200, 260, 320;
  0, 25, 50,  90, 130, 190, 250, 325, 400, 499;
  0, 30, 60, 108, 156, 228, 300, 390, 480, 598, 716;
  ...

M. A. Alekseyev. On the number of two-dimensional threshold functions. SIAM J. Disc. Math. 24(4), 2010, pp. 1617-1631. doi:10.1137/090750184
M. A. Alekseyev, M. Basova, N. Yu. Zolotykh. On the minimal teaching sets of two-dimensional threshold functions. SIAM J. Disc. Math. 29(1), 2015, pp. 157-165.

Cf. A115004, A114999, A320541.
The main diagonal is A331761.
See A335683 for another version.

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

Table[Sum[Boole[GCD[i, j] == 2] (n + 1 - i) (k + 1 - j), {i, n}, {j, k}], {n, 11}, {k, n}] // Flatten (* Michael De Vlieger, Feb 04 2020 *)

A320539 (1/2) * number of ways to select 3 distinct collinear points from a rectangle of grid points with side lengths j and k, written as triangle T(j,k), j<=k.

Original entry on oeis.org

0, 1, 4, 4, 10, 22, 10, 21, 42, 76, 20, 39, 70, 120, 186, 35, 65, 112, 184, 279, 412, 56, 100, 166, 264, 390, 566, 772, 84, 146, 236, 367, 532, 759, 1026, 1356, 120, 205, 324, 494, 704, 991, 1326, 1740, 2224, 165, 278, 432, 647, 913, 1271, 1686, 2196, 2793, 3496

Offset: 1

Hugo Pfoertner, Oct 15 2018

Permutations of the 3 points are not counted separately.

			The triangle begins:
    0
    1    4
    4   10   22
   10   21   42   76
   20   39   70  120  186
   35   65  112  184  279  412
   56  100  166  264  390  566  772
.
a(2) = T(1,2) = 1, because the grid points on the two longer sides of the rectangle are collinear: (0,0) (0,1) (0,2) and (1,0) (1,1) (2,2).
a(3) = T(2,2) = 4, because there are 8 triples of collinear points:
  (0,0) (0,1) (0,2),
  (0,0) (1,0) (2,0),
  (0,0) (1,1) (2,2),
  (0,1) (1,1) (2,1),
  (0,2) (1,1) (2,0),
  (0,2) (1,2) (2,2),
  (1,0) (1,1) (1,2),
  (2,0) (2,1) (2,2).

A000292, A320540, A320541, A320543.

A320543 (1/2) * number of ways to select 3 distinct points forming a triangle of unsigned area = 1 from a rectangle of grid points with side lengths j and k, written as triangle T(j,k), j<=k.

Original entry on oeis.org

0, 3, 16, 8, 35, 72, 15, 62, 125, 212, 24, 95, 190, 319, 476, 35, 136, 269, 450, 669, 936, 48, 183, 360, 601, 892, 1245, 1652, 63, 238, 467, 776, 1149, 1602, 2123, 2724, 80, 299, 584, 967, 1430, 1991, 2636, 3379, 4188, 99, 368, 717, 1186, 1751, 2436, 3223, 4130, 5117, 6248

Offset: 1

Hugo Pfoertner, Oct 16 2018

			The triangle begins:
   0
   3  16
   8  35  72
  15  62 125 212
  24  95 190 319 476
  35 136 269 450 669 936
.
a(2) = T(1,2) = 3 = 6/2 because the following 6 triangles of area 1 can be made by selecting 3 grid points from the [0,1]X[0,2] rectangle:
  (0,0) (0,2) (1,0),
  (0,0) (0,2) (1,1),
  (0,0) (0,2) (1,2),
  (0,0) (1,0) (1,2),
  (0,1) (1,0) (1,2),
  (0,2) (1,0) (1,2).

Cf. A005563, A320539, A320541, A320544.

A333292 Triangle read by rows: T(m,n) = Sum_{ 1 <= i <= m, 1 <= j <= n, gcd(i,j)=1 } i*j, for 1 <= n <= m.

Original entry on oeis.org

1, 3, 5, 6, 14, 23, 10, 18, 39, 55, 15, 33, 69, 105, 155, 21, 39, 75, 111, 191, 227, 28, 60, 117, 181, 296, 374, 521, 36, 68, 149, 213, 368, 446, 649, 777, 45, 95, 176, 276, 476, 554, 820, 1020, 1263, 55, 105, 216, 316, 516, 594, 930, 1130, 1463, 1663, 66, 138, 282, 426, 681, 825, 1238, 1526, 1958, 2268, 2873

Offset: 1

N. J. A. Sloane, Mar 23 2020

The last two diagonals are A333293, Sum_{k=1..n-1} k^2*phi(k) + n^2*phi(n)/2, and A319087, Sum_{k=1..n} k^2*phi(k), where phi = A000010. Is there a similar formula for the general term?

			Triangle begins:
1,
3, 5,
6, 14, 23,
10, 18, 39, 55,
15, 33, 69, 105, 155,
21, 39, 75, 111, 191, 227,
28, 60, 117, 181, 296, 374, 521,
36, 68, 149, 213, 368, 446, 649, 777,
45, 95, 176, 276, 476, 554, 820, 1020, 1263,
55, 105, 216, 316, 516, 594, 930, 1130, 1463, 1663,
...

Alois P. Heinz, Rows n = 1..141, flattened

First two columns are A000217 and A074378, rightmost two diagonals are A333293 and A319087.
Main diagonal is A319087.
Cf. A320541.

T:= (m, n)-> add(add(`if`(igcd(i, j)=1, i*j, 0), j=1..n), i=1..m):
seq(seq(T(m, n), n=1..m), m=1..12);  # Alois P. Heinz, Mar 23 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);

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Python

Formula

A114999 Array read by antidiagonals: T(m,n) = Sum_{i=1..m, j=1..n, gcd(i,j)=1} (m+1-i)*(n+1-j), m>=1, n>=1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A331762 Triangle read by rows: T(n,k) (1 <= k <= n) = Sum_{i=1..n, j=1..k, gcd(i,j)=2} (n+1-i)*(k+1-j).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A320539 (1/2) * number of ways to select 3 distinct collinear points from a rectangle of grid points with side lengths j and k, written as triangle T(j,k), j<=k.

Views

Author

Keywords

Comments

Examples

Crossrefs

A320543 (1/2) * number of ways to select 3 distinct points forming a triangle of unsigned area = 1 from a rectangle of grid points with side lengths j and k, written as triangle T(j,k), j<=k.

Views

Author

Keywords

Examples

Crossrefs

A333292 Triangle read by rows: T(m,n) = Sum_{ 1 <= i <= m, 1 <= j <= n, gcd(i,j)=1 } i*j, for 1 <= n <= m.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

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