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

Author

Seppo Mustonen, May 28 2009

Keywords

• nonn

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

Crossrefs

5th row/column of A107348, A295707.

Programs

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}]

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)