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

Author

Seppo Mustonen, May 13 2010

Keywords

• nonn

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]

Programs

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}]

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

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