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,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=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)

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

Crossrefs

Column k=9 of A295707.

Sequence in context: A142118 A044253 A044634 * A277807 A246874 A136079

Adjacent sequences: A160846 A160847 A160848 * A160850 A160851 A160852

Keyword

nonn

Author

Seppo Mustonen, May 28 2009

Status

approved