A160847 Number of lines through at least 2 points of a 7 X n grid of points.

0, 1, 51, 100, 181, 274, 405, 536, 709, 894, 1111, 1330, 1591, 1858, 2167, 2482, 2825, 3180, 3577, 3974, 4413, 4860, 5339, 5824, 6351, 6884, 7455, 8032, 8641, 9262, 9925, 10584, 11285, 11998, 12743, 13494, 14283, 15078, 15915, 16758, 17633, 18516

Offset

0,3

Links

Seiichi Manyama, Table of n, a(n) for n = 0..1000

S. Mustonen, On lines and their intersection points in a rectangular grid of points

Formula

a(n) = (1/2)*(f(m,n,1)-f(m,n,2)) where f(m,n,k) = Sum((n - |kx|)*(m - |ky|)); -n < kx <n, -m < ky <m, (x,y)=1, m=7.

For another more efficient formula, see Mathematica code below.

Empirical g.f.: -x*(7*x^14 + 8*x^12 + 43*x^11 + 50*x^10 + 117*x^9 + 135*x^8 + 204*x^7 + 173*x^6 + 211*x^5 + 142*x^4 + 131*x^3 + 50*x^2 + 50*x + 1) / ((x - 1)^3*(x + 1)*(x^2 - x + 1)*(x^2 + 1)*(x^2 + x + 1)*(x^4 + x^3 + x^2 + x + 1)). - Colin Barker, May 24 2015

Mathematica

m=7;
a[0]=0; a[1]=1;
a[2]=m^2+2;
a[3]=2*m^2+3-Mod[m, 2];
a[n_]:=a[n]=2*a[n-1]-a[n-2]+2*p1[m, n]+2*p4[m, n]
p1[m_, n_]:=Sum[p2[m, n, y], {y, 1, m-1}]
p2[m_, n_, y_]:=If[GCD[y, n-1]==1, m-y, 0]
p[i_]:=If[i>0, i, 0]
p2[m_, n_, x_, y_]:=p2[m, n, x, y]=(n-x)*(m-y)-p[n-2*x]*p[m-2*y]
p3[m_, n_, x_, y_]:=p2[m, n, x, y]-2*p2[m, n-1, x, y]+p2[m, n-2, x, y]
p4[m_, n_]:=p4[m, n]=If[Mod[n, 2]==0, 0, p42[m, n]]
p42[m_, n_]:=p42[m, n]=Sum[p43[m, n, y], {y, 1, m-1}]
p43[m_, n_, y_]:=If[GCD[(n-1)/2, y]==1, p3[m, n, (n-1)/2, y], 0]
Table[a[n], {n, 0, 41}]

Crossrefs

Sequence in context: A229274 A044140 A044521 * A260517 A235878 A015705

Adjacent sequences: A160844 A160845 A160846 * A160848 A160849 A160850

Keyword

nonn

Author

Seppo Mustonen, May 28 2009

Status

approved