|
%I #13 Aug 18 2021 15:33:19
%S 0,0,8,24,60,112,212,344,548,800,1196,1672,2284,2992,3988,5128,6556,
%T 8160,10180,12424,15068,17968,21604,25576,30092,34976,40900,47288,
%U 54500,62224,70972,80296,90740,101824,114700,128344,143212,158896,176836
%N Number of line segments connecting exactly 3 points in an n X n grid of points
%C 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 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 Chai Wah Wu, <a href="/A177719/b177719.txt">Table of n, a(n) for n = 1..10000</a>
%H 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 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 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 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 j=2;
%t a[n_]:=a[n]=If[n<=j,0,2*a1[n]-a[n-1]+R1[n]]
%t a1[n_]:=a1[n]=If[n<=j,0,2*a[n-1]-a1[n-1]+R2[n]]
%t R1[n_]:=R1[n]=If[n<=j,0,R1[n-1]+4*S[n]]
%t R2[n_]:=(n-1)*S[n]
%t S[n_]:=If[Mod[n-1,j]==0,EulerPhi[(n-1)/j],0]
%t Table[a[n],{n,1,50}]
%o (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 (Python)
%o from sympy import totient
%o 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 nonn
%O 1,3
%A _Seppo Mustonen_, May 13 2010
|
