A177719 Number of line segments connecting exactly 3 points in an n X n grid of points

0, 0, 8, 24, 60, 112, 212, 344, 548, 800, 1196, 1672, 2284, 2992, 3988, 5128, 6556, 8160, 10180, 12424, 15068, 17968, 21604, 25576, 30092, 34976, 40900, 47288, 54500, 62224, 70972, 80296, 90740, 101824, 114700, 128344, 143212, 158896, 176836

Offset

1,3

Comments

a(n) is also the number of pairs of points visible to each other exactly through one point in an n X n grid of points.

Mathematica code below computes with j=1 also A114043(n)-1 and A141255(n) much more efficiently than codes/formulas currently presented for those sequences.

Links

Chai Wah Wu, Table of n, a(n) for n = 1..10000

Seppo Mustonen, On lines going through a given number of points in a rectangular grid of points

Seppo Mustonen, On lines going through a given number of points in a rectangular grid of points [Local copy]

Formula

a(n) = Sum_{-n < i,j < n; gcd(i,j)=2} (n-|i|)*(n-|j|)/2. For n>1, a(n) = 2 * ( n*(n-2) + Sum_{i,j=1..n-1; gcd(i,j)=2} (n-i)*(n-j) ). - Max Alekseyev, Jul 08 2019

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

Mathematica

j=2;
a[n_]:=a[n]=If[n<=j, 0, 2*a1[n]-a[n-1]+R1[n]]
a1[n_]:=a1[n]=If[n<=j, 0, 2*a[n-1]-a1[n-1]+R2[n]]
R1[n_]:=R1[n]=If[n<=j, 0, R1[n-1]+4*S[n]]
R2[n_]:=(n-1)*S[n]
S[n_]:=If[Mod[n-1, j]==0, EulerPhi[(n-1)/j], 0]
Table[a[n], {n, 1, 50}]

Prog

(PARI) { A177719(n) = if(n<2, return(0)); 2*(n*(n-2) + sum(i=1, n-1, sum(j=1, n-1, (gcd(i, j)==2)*(n-i)*(n-j))) ); } \\ Max Alekseyev, Jul 08 2019
(Python)
from sympy import totient
def A177719(n): return 4*((n-1)*(n-2) + sum(totient(i)*(n-2*i)*(n-i) for i in range(2, n//2+1))) # Chai Wah Wu, Aug 18 2021

Crossrefs

Sequence in context: A306056 A129959 A256533 * A317234 A049724 A060602

Adjacent sequences: A177716 A177717 A177718 * A177720 A177721 A177722

Keyword

nonn

Author

Seppo Mustonen, May 13 2010

Status

approved