A222267 The number of distinct lines defined by an n X n X n grid of points.

28, 253, 1492, 5485, 17092, 41905, 95140, 191773, 364420, 638785, 1085500, 1745389, 2743084, 4136257, 6101740, 8747821, 12377764, 17066737, 23287564, 31174813, 41276548, 53767873, 69544324, 88722973, 112450132, 140859361, 175324636

Offset: 2

Author

Clive Tooth, Feb 13 2013

Keywords

• nonn
• nice

Comments

Given a cubic n X n X n grid of points, a(n) is the number of distinct lines produced by constructing a line through every pair of points.

Define the grid as consisting of the set of n^3 distinct points whose x, y and z coordinates are all integers in [0..n-1]. Assign to each grid point a distinct index j = x + n*y + n^2*z. For each pair of grid points P_A and P_B (where P_A is the one with the lower index j), let L be the line that passes through both grid points, and let S be the segment of that line from P_A to P_B. Examine each of the C(n^3,2) pairs of distinct grid points P_A and P_B; a(n) is the number of those pairs for which S does not pass through any other grid points between P_A and P_B, nor does L pass through any other grid points beyond the P_A end of S. - Jon E. Schoenfield, Sep 21 2013

Conjecture: a(n) is approximately 0.3639537*n^6, with a relative error of about 10^-5 when n is near 200. - Clive Tooth, Mar 03 2016

Examples

			Each of the 28 pairs of points on a 2 X 2 X 2 grid of points defines a distinct line, so a(2) = 28.
Of the 351 pairs of points on a 3 X 3 X 3 grid, there are only 253 distinct lines, so a(3) = 253.
		

Links

• Clive Tooth, Table of n, a(n) for n = 2..200 (using a method of Haukkanen & Merikoski) [Terms 2 through 70 were computed by Jon E. Schoenfield]
• P. Haukkanen, J. K. Merikoski, Some formulas for numbers of line segments and lines in a rectangular grid, arXiv:1108.1041 [math.CO], 2011.
• Clive Tooth, A C# class declaration

Crossrefs

Cf. A018808, A222268 (number of intersection points of these lines).

Programs

Mathematica

mq[{x1_, y1_}, {x2_, y2_}] := If[x1 == x2, {x1}, {y2 - y1, x2*y1 - x1*y2}/(x2 - x1)]; two[n_] := Block[{p = Tuples[Range@n, 2]},
Length@Union@Flatten[Table[mq[p[[i]], p[[j]]], {i, 2, n^2}, {j, i - 1}], 1]]; coef[a_, b_] := Block[{d = b - a}, If[d[[1]] == 0, {0}, d *= Sign@d[[1]]/GCD @@ d; {a - d*a[[1]]/d[[1]], d}]]; a[n_] := Block[{p = Tuples[Range@n, 3]}, n*two[n] - 1 + Length@Union@ Flatten[Table[coef[p[[i]], p[[j]]], {i, 2, n^3}, {j, i - 1}], 1]]; Table[v = a[n]; Print@v; v, {n, 2, 12}] (* Giovanni Resta, Feb 14 2013 *)

Extensions

a(6)-a(12) from Giovanni Resta, Feb 14 2013

a(13)-a(28) from Jon E. Schoenfield, Sep 16 2013