A141255 Total number of line segments between points visible to each other in a square n X n lattice.
0, 6, 28, 86, 200, 418, 748, 1282, 2040, 3106, 4492, 6394, 8744, 11822, 15556, 20074, 25456, 32086, 39724, 48934, 59456, 71554, 85252, 101250, 119040, 139350, 161932, 187254, 215136, 246690, 280916, 319346, 361328, 407302, 457180, 511714, 570232
Offset: 1
Keywords
Examples
The 2 x 2 square lattice has a total of 6 line segments: 2 vertical, 2 horizontal and 2 diagonal.
References
- D. M. Acketa, J. D. Zunic: On the number of linear partitions of the (m,n)-grid. Inform. Process. Lett., 38 (3) (1991), 163-168. See Table A.1.
- Jovisa Zunic, Note on the number of two-dimensional threshold functions, SIAM J. Discrete Math. Vol. 25 (2011), No. 3, pp. 1266-1268. See Eq. (1.2).
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 [From _Seppo Mustonen_, May 13 2010]
- Seppo Mustonen, On lines going through a given number of points in a rectangular grid of points [Local copy]
- N. J. A. Sloane, Families of Essentially Identical Sequences, Mar 24 2021 (Includes this sequence)
Crossrefs
Cf. A141224.
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. - N. J. A. Sloane, Feb 04 2020
Programs
-
Mathematica
Table[cnt=0; Do[If[GCD[c-a,d-b]<2, cnt++ ], {a,n}, {b,n}, {c,n}, {d,n}]; (cnt-n^2)/2, {n,20}] (* This recursive code is much more efficient. *) a[n_]:=a[n]=If[n<=1,0,2*a1[n]-a[n-1]+R1[n]] a1[n_]:=a1[n]=If[n<=1,0,2*a[n-1]-a1[n-1]+R2[n]] R1[n_]:=R1[n]=If[n<=1,0,R1[n-1]+4*EulerPhi[n-1]] R2[n_]:=(n-1)*EulerPhi[n-1] Table[a[n],{n,1,37}] (* Seppo Mustonen, May 13 2010 *) a[n_]:=2 Sum[(n-i) (n-j) Boole[CoprimeQ[i,j]], {i,1,n-1}, {j,1,n-1}] + 2 n^2 - 2 n; Array[a, 40] (* Vincenzo Librandi, Feb 05 2020 *) -
Python
from sympy import totient def A141255(n): return 2*(n-1)*(2*n-1) + 2*sum(totient(i)*(n-i)*(2*n-i) for i in range(2,n)) # Chai Wah Wu, Aug 16 2021
Formula
a(n) = A114043(n) - 1.
a(n) = 2*(n-1)*(2n-1) + 2*Sum_{i=2..n-1} (n-i)*(2n-i)*phi(i). - Chai Wah Wu, Aug 16 2021
Comments