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

0, 0, 2, 11, 32, 77, 148, 268, 442, 691, 1018, 1472, 2036, 2780, 3686, 4786, 6100, 7724, 9598, 11863, 14454, 17437, 20818, 24772, 29172, 34200, 39794, 46071, 52986, 60817, 69314, 78860, 89292, 100720, 113122, 126686, 141244, 157294, 174566, 193228, 213172, 234954, 258058, 283189, 309946, 338473, 368782, 401516, 436040

Offset: 1

Author

Scott R. Shannon and N. J. A. Sloane, Mar 14 2020

Keywords

• nonn

Comments

Related to the number of linear dichotomies on a square grid.

A331771(n) = 8*a(n) + 4*n*(n-1) + 4*(n-1)^2.

Links

• Seiichi Manyama, Table of n, a(n) for n = 1..1000
• Jack Koplowitz, Michael Lindenbaum, and A. Bruckstein, The number of digital straight lines on an NxN grid, IEEE Transactions on Information Theory 36.1 (1990): 192-197. (See I_1.)

Crossrefs

The following eight sequences are all essentially the same. The simplest is 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. The present sequence and A331771 could be added to this list.

Programs

Maple

I1 := proc(n) local a, i, j; a:=0;
for i from 2 to n-1 do for j from 1 to i-1 do
if igcd(i,j)=1 then a := a+(n-i)*(n-j); fi; od; od; a; end;
[seq(I1(n),n=1..40)];

PARI

a(n) = sum(i=2, n-1, sum(j=1, i-1, if (gcd(i,j)==1, (n-i)*(n-j)))); \\ Michel Marcus, Mar 14 2020

Python

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

Formula

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