A225606 Number of distinct lines passing through 3 or more points in an n X n grid.

0, 0, 0, 8, 14, 32, 58, 108, 174, 296, 406, 628, 898, 1216, 1582, 2188, 2754, 3528, 4398, 5524, 6778, 8336, 9778, 11812, 14038, 16456, 19066, 22540, 25954, 29968, 34270, 39116, 44282, 50312, 56026, 63196, 70798, 78984

Offset: 0

Author

R. J. Mathar, Aug 06 2013

Keywords

• nonn

Links

• P. Haukkanen, J. K. Merikoski, Some formulas for numbers of line segments and lines in a rectangular grid, arXiv:1108.1041
• R. J. Mathar, Maple program implementing A225606, A018808 and sequ. in comment of A187397

Programs

Mathematica

f[n_, k_] := Sum[x = kx/k; y = ky/k; If[IntegerQ[x] && IntegerQ[y] && CoprimeQ[x, y], (n - Abs[kx])(n - Abs[ky]), 0], {kx, -n + 1, n - 1}, {ky, -n + 1, n - 1}];
a[n_] := (f[n, 2] - f[n, 3])/2;
Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Oct 30 2018, after Seppo Mustonen in A018808 *)

Formula

a(n) = A018808(n) - A018809(n) = A018810(n) + A018811(n) + A018812(n) + A018813(n)+....