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

0, 1, 4, 15, 32, 71, 124, 211, 320, 499, 716, 999, 1328, 1799, 2340, 3023, 3792, 4767, 5852, 7135, 8544, 10319, 12260, 14471, 16864, 19775, 22916, 26467, 30272, 34587, 39188, 44347, 49824, 56195, 62948, 70311, 78080, 86975

Offset: 1

Author

N. J. A. Sloane, Feb 04 2020

Keywords

• nonn

Links

• Chai Wah Wu, Table of n, a(n) for n = 1..10000 (terms n=1..600 from N. J. A. Sloane)
• M. A. Alekseyev. On the number of two-dimensional threshold functions. arXiv:math/0602511 [math.CO], 2006-2009; doi:10.1137/090750184, SIAM J. Disc. Math. 24(4), 2010, pp. 1617-1631.
• M. A. Alekseyev, M. Basova and N. Yu. Zolotykh. On the minimal teaching sets of two-dimensional threshold functions, SIAM J. Disc. Math. 29(1), 2015, pp. 157-165.

Crossrefs

Cf. A115004.

The main diagonal of A331762.

Programs

Mathematica

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

Python

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

Formula

Conjecture: As n -> oo, a(n) ~ C*n^4/Pi^2, where C is about 0.3775. - N. J. A. Sloane, Jul 03 2020

a(n) = (n-1)^2 + 2*Sum_{i=2..floor(n/2)} (n+1-2*i)*(n+1-i)*phi(i). - Chai Wah Wu, Aug 16 2021