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

%I #77 May 08 2024 06:03:37

%S 1,8,31,80,179,332,585,948,1463,2136,3065,4216,5729,7568,9797,12456,

%T 15737,19520,24087,29308,35315,42120,50073,58920,69025,80264,92871,

%U 106756,122475,139528,158681,179608,202529,227400,254597,283784,315957,350576,387977

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

%C 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

%C From _Chai Wah Wu_, Aug 18 2021: (Start)

%C Theorem: a(n) = n^2 + Sum_{i=2..n} (n+1-i)*(2*n+2-i)*phi(i).

%C 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)

%C = 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.

%C 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.

%C Similar argument holds for corresponding formulas for A088658, A114043, A114146, A115005, etc.

%C (End)

%H Ray Chandler, <a href="/A115004/b115004.txt">Table of n, a(n) for n = 1..1000</a>

%H M. Griffiths, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL13/Griffiths2/griffiths.html">Counting the regions in a regular drawing of K_{n,n}</a>, J. Int. Seq. 13 (2010) # 10.8.5.

%H S. Legendre, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL12/Legendre/legendre2.html">The Number of Crossings in a Regular Drawing of the Complete Bipartite Graph</a>, JIS 12 (2009) 09.5.5.

%H R. J. Mathar, <a href="/A115004/a115004.pdf">Graphical representation among sequences closely related to this one</a> (cf. N. J. A. Sloane, "Families of Essentially Identical Sequences").

%H N. J. A. Sloane, <a href="/A115004/a115004.txt">Families of Essentially Identical Sequences</a>, Mar 24 2021. (Includes this sequence)

%H N. J. A. Sloane (in collaboration with Scott R. Shannon), <a href="/A331452/a331452.pdf">Art and Sequences</a>, Slides of guest lecture in Math 640, Rutgers Univ., Feb 8, 2020. Mentions this sequence.

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

%F 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

%F a(n) = n^2 + Sum_{i=2..n} (n+1-i)*(2n+2-i)*phi(i). - _Chai Wah Wu_, Aug 15 2021

%p A115004 := proc(n)

%p local a,b,r ;

%p r := 0 ;

%p for a from 1 to n do

%p for b from 1 to n do

%p if igcd(a,b) = 1 then

%p r := r+(n+1-a)*(n+1-b);

%p end if;

%p end do:

%p end do:

%p r ;

%p end proc:

%p seq(A115004(n),n=1..30); # _R. J. Mathar_, Jul 20 2017

%t a[n_] := Sum[(n-i+1) (n-j+1) Boole[GCD[i, j] == 1], {i, n}, {j, n}];

%t Array[a, 40] (* _Jean-François Alcover_, Mar 23 2020 *)

%o (Python)

%o from math import gcd

%o def a115004(n):

%o r=0

%o for a in range(1, n + 1):

%o for b in range(1, n + 1):

%o if gcd(a, b)==1:

%o r+=(n + 1 - a)*(n + 1 - b)

%o return r

%o print([a115004(n) for n in range(1, 51)]) # _Indranil Ghosh_, Jul 21 2017

%o (Python)

%o from sympy import totient

%o 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

%o (PARI) a(n) = n^2 + sum(i=2, n, (n+1-i)*(2*n+2-i)*eulerphi(i)); \\ _Michel Marcus_, May 08 2024

%Y Cf. A320540, A320541, A320544.

%Y 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

%Y Main diagonal of array in A114999.

%K nonn,nice

%O 1,2

%A _N. J. A. Sloane_, Feb 23 2006