cp's OEIS Frontend

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

%I A177719 #15 Jul 22 2025 08:09:17
%S A177719 0,0,8,24,60,112,212,344,548,800,1196,1672,2284,2992,3988,5128,6556,
%T A177719 8160,10180,12424,15068,17968,21604,25576,30092,34976,40900,47288,
%U A177719 54500,62224,70972,80296,90740,101824,114700,128344,143212,158896,176836
%N A177719 Number of line segments connecting exactly 3 points in an n X n grid of points.
%C A177719 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.
%C A177719 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.
%H A177719 Chai Wah Wu, <a href="/A177719/b177719.txt">Table of n, a(n) for n = 1..10000</a>
%H A177719 Seppo Mustonen, <a href="http://www.survo.fi/papers/LinesInGrid2.pdf">On lines going through a given number of points in a rectangular grid of points</a>
%H A177719 Seppo Mustonen, <a href="/A141255/a141255.pdf">On lines going through a given number of points in a rectangular grid of points</a> [Local copy]
%F A177719 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
%F A177719 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
%t A177719 j=2;
%t A177719 a[n_]:=a[n]=If[n<=j,0,2*a1[n]-a[n-1]+R1[n]]
%t A177719 a1[n_]:=a1[n]=If[n<=j,0,2*a[n-1]-a1[n-1]+R2[n]]
%t A177719 R1[n_]:=R1[n]=If[n<=j,0,R1[n-1]+4*S[n]]
%t A177719 R2[n_]:=(n-1)*S[n]
%t A177719 S[n_]:=If[Mod[n-1,j]==0,EulerPhi[(n-1)/j],0]
%t A177719 Table[a[n],{n,1,50}]
%o A177719 (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
%o A177719 (Python)
%o A177719 from sympy import totient
%o A177719 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
%K A177719 nonn
%O A177719 1,3
%A A177719 _Seppo Mustonen_, May 13 2010