A320540 -id:A320540 - 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

A320544 (1/8) * number of ways to select 3 distinct points forming a triangle of unsigned area = 1 from a square of grid points with side length n.

Original entry on oeis.org

0, 4, 18, 53, 119, 234, 413, 681, 1047, 1562, 2243, 3101, 4186, 5576, 7231, 9243, 11652, 14518, 17886, 21779, 26191, 31368, 37285, 43919, 51364, 59894, 69338, 79831, 91495, 104336, 118513, 134135, 151072, 169878, 190229, 212185, 236040, 262244, 290317, 320487

Offset: 1

Hugo Pfoertner, Oct 21 2018

nonn

Permutations of the 3 points are not counted separately.

			a(1) = 0 because no triangle of area 1 can be formed from the corner points of the [0,1]X[0,1] square.
a(2) = 4 because 3 triangles of area 1 can be formed by connecting the end points of any of the 8 segments of length 1 on the periphery of the [0,2]X[0,2] square to any of the 3 vertices on the opposite side of the grid square, making 8*3 = 24 triangles. Additionally, 4 triangles of the type (0,0),(0,2),(1,2) and another 4 triangles of the type (2,1),(0,1),(1,0) can be selected. 24 + 4 + 4 = 32, a(2) = 32/8 = 4.

Giovanni Resta, Table of n, a(n) for n = 1..100

Diagonal of A320543.

Cf. A115004, A320540.

a(27)-a(40) from Giovanni Resta, Oct 26 2018

A320310 (1/4) * number of ways to select 3 distinct points forming a triangle of unsigned area = n/2 from a square of grid points with side length n.

Original entry on oeis.org

1, 8, 23, 82, 114, 416, 373, 1149, 1351, 2598, 2113, 7158, 4094, 9344, 11528, 18243, 11882, 33006, 18603, 48760, 42102, 54312, 40061, 121728, 68115, 105204, 112546, 178322, 101798, 284980, 133229, 300367, 247900, 305062, 295972, 625544, 271864, 475004, 479658, 847208

Offset: 1

Hugo Pfoertner, Oct 23 2018

nonn

Permutations of the 3 points are not counted separately.

Giovanni Resta, Table of n, a(n) for n = 1..100

Cf. A115004, A320540, A320542, A320544.

a(35)-a(40) from Giovanni Resta, Oct 26 2018

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.

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

A320542 a(n) is the number of ways to select 3 distinct points forming a triangle of unsigned area = n from a square of grid points with side length n, divided by 4.

Original entry on oeis.org

0, 2, 12, 33, 74, 258, 294, 661, 1258, 1940, 2044, 5254, 4136, 7738, 12902, 13357, 13142, 29540, 21214, 40816, 50388, 50012, 47680, 101662, 83684, 99690, 140638, 158568, 126720, 282042, 167514, 253779, 318556, 302230, 386186, 579833, 350556, 478058, 629582, 765498

Offset: 1

Hugo Pfoertner, Oct 15 2018

nonn

Let s(n) be the number of ways to select 3 different points from a square of grid points with side length n such that they form a triangle with absolute area n, then a(n) = s(n)/4. Permutations of the vertices are considered equivalent.

Cf. A115004, A320310, A320540, A320544.

a(35)-a(40) from Giovanni Resta, Oct 26 2018

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

A320544 (1/8) * number of ways to select 3 distinct points forming a triangle of unsigned area = 1 from a square of grid points with side length n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A320310 (1/4) * number of ways to select 3 distinct points forming a triangle of unsigned area = n/2 from a square of grid points with side length n.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

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

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

A320542 a(n) is the number of ways to select 3 distinct points forming a triangle of unsigned area = n from a square of grid points with side length n, divided by 4.

Views

Author

Keywords

Comments

Crossrefs

Extensions