|
%I #74 Sep 05 2023 01:55:44
%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
%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
|
