A160849 Number of lines through at least 2 points of a 9 X n grid of points.

0, 1, 83, 164, 299, 454, 673, 894, 1183, 1492, 1855, 2218, 2653, 3102, 3623, 4148, 4719, 5310, 5973, 6638, 7375, 8124, 8923, 9730, 10609, 11502, 12459, 13424, 14443, 15478, 16585, 17686, 18859, 20052, 21299, 22554, 23869, 25198, 26599, 28008

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

Column k=9 of A295707.

Programs

Mathematica

m=9;
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,39}]

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

For another more efficient formula, see Mathematica code below.

Conjectures from Colin Barker, Dec 25 2017: (Start)

G.f.: x*(1 + 83*x + 165*x^2 + 382*x^3 + 618*x^4 + 971*x^5 + 1264*x^6 + 1607*x^7 + 1756*x^8 + 1873*x^9 + 1738*x^10 + 1571*x^11 + 1228*x^12 + 935*x^13 + 600*x^14 + 373*x^15 + 174*x^16 + 92*x^17 + 19*x^18 + 9*x^19 + 9*x^20) / ((1 - x)^3*(1 + x)*(1 - x + x^2)*(1 + x^2)*(1 + x + x^2)*(1 + x + x^2 + x^3 + x^4)*(1 + x + x^2 + x^3 + x^4 + x^5 + x^6)).

a(n) = -a(n-2) + a(n-5) + a(n-6) + 2*a(n-7) + a(n-8) + a(n-9) - a(n-11) - a(n-12) - 2*a(n-13) - a(n-14) - a(n-15) + a(n-18) + a(n-20) for n>21.

(End)