login
A332612
a(n) = Sum_{ i=2..n-1, j=1..i-1, gcd(i,j)=1 } (n-i)*(n-j).
3
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,3
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
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.)
FORMULA
a(n) = (Sum_{i=2..n-1} (n-i)*(2n-i)*phi(i))/2. - Chai Wah Wu, Aug 17 2021
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)];
PROG
(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
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.
Sequence in context: A023659 A094792 A173707 * A192347 A031400 A085786
KEYWORD
nonn
AUTHOR
STATUS
approved