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

A320540 (1/4) * number of ways to select 3 distinct collinear points from a square of grid points with side length n.

Original entry on oeis.org

0, 2, 11, 38, 93, 206, 386, 678, 1112, 1748, 2583, 3768, 5253, 7172, 9630, 12720, 16370, 20910, 26169, 32566, 40139, 48962, 58900, 70710, 84096, 99284, 116469, 136116, 157671, 182436, 209436, 239596, 272976, 309630, 350035, 395346, 444021, 496890, 554402, 617906

Offset: 1

Hugo Pfoertner, Oct 15 2018

nonn

Permutations of the 3 points are not counted separately.

			a(2) = 2 because there are 8 triples of collinear points in the square [0 2] X [0 2]: The 2*3 lines of x=0,1,2 and y=0,1,2 and the 2 diagonals.

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

(1/2)* diagonal of triangle A320539.

Cf. A115004, A320544.

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

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.

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

A372915 a(n) is the number of distinct triangles with area n whose vertices are points of an n X n grid.

Original entry on oeis.org

0, 0, 2, 4, 9, 10, 25, 22, 38, 49, 56, 56, 111, 71, 119, 141, 153, 126, 249, 166, 244, 299, 279, 244, 463, 288, 361, 489, 517, 373, 677, 436, 626, 719, 620, 665, 1078, 604, 811, 936, 1000, 749, 1444, 842, 1221, 1384, 1173, 1016, 1871, 1261, 1393, 1597, 1566, 1259

Offset: 0

Felix Huber, Jun 02 2024

nonn

			See the linked illustration for the term a(4) = 9.

Felix Huber, Table of n, a(n) for n=0..666
Felix Huber, Illustration of the term a(4) = 9

Cf. A045996, A088658, A303331, A320310, A320542, A320544, A334713, A372217, A372218.

A372915:=proc(n)
  local p,q,g,h,u,v,x,y,L,M;
  L:=[];
  for g from 2 to n do
    h:=2*n/g;
    if type(h,integer) then
      for x to n do
        M:=[g,sqrt(x^2+h^2),sqrt((g-x)^2+h^2)];
        M:=sort(M);
        if not member(M,L) then
          L:=[op(L),M];
        fi;
      od;
    fi;
  od;
  for p to n do
    for q from 1 to p do
      g:=sqrt(p^2+q^2);
      h:=2*n/g;
      u:=h/g*q;
      v:=q+h/g*p;
      for x from max(1,ceil(p/q*(v-n)+u)) to min(n,floor(p/q*v+u)) do
        y:=q/p*(u-x)+v;
        if type(y,integer) and x <> p and y <> q then
          M:=[g,sqrt(x^2+(y-q)^2),sqrt((x-p)^2+y^2)];
          M:=sort(M);
          if not member(M,L) then
            L:=[op(L),M];
          fi;
        fi;
      od;
    od;
  od;
  return numelems(L);
end proc;
seq(A372915(n),n=0..53);

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

A320540 (1/4) * number of ways to select 3 distinct collinear points 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

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

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

A372915 a(n) is the number of distinct triangles with area n whose vertices are points of an n X n grid.

Views

Author

Keywords

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