A160845 Number of lines through at least 2 points of a 5 X n grid of points.

0, 1, 27, 52, 93, 140, 207, 274, 361, 454, 563, 676, 809, 944, 1099, 1258, 1433, 1614, 1815, 2016, 2237, 2464, 2707, 2954, 3221, 3490, 3779, 4072, 4381, 4696, 5031, 5366, 5721, 6082, 6459, 6840, 7241, 7644, 8067, 8494, 8937, 9386, 9855, 10324, 10813

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=5.

For another more efficient formula, see Mathematica code below.

Conjectures from Colin Barker, May 24 2015: (Start)

a(n) = a(n-1) + a(n-3) - a(n-5) - a(n-7) + a(n-8) for n > 7.

G.f.: x*(5*x^8 + x^6 + 16*x^5 + 20*x^4 + 40*x^3 + 25*x^2 + 26*x + 1) / ((1 - x)^3*(x + 1)*(x^2 + 1)*(x^2 + x + 1)).

(End)

Mathematica

m=5;
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, 44}]

Crossrefs

5th row/column of A107348, A295707.

Sequence in context: A265683 A044079 A044460 * A216224 A255364 A082915

Adjacent sequences: A160842 A160843 A160844 * A160846 A160847 A160848

Keyword

nonn

Author

Seppo Mustonen, May 28 2009

Status

approved