A157882 Number of collinear point-triples in the n X n X n cube.

0, 0, 49, 376, 1858, 5696, 16427, 36992, 78204, 150672, 277005, 463624, 776494, 1212208, 1845911, 2749568, 4023608, 5654976, 7915497, 10730616, 14487706, 19290352, 25343011, 32580752, 41959412, 53240624, 66913605, 83330712

Offset: 1

Author

R. J. Mathar, May 21 2010

Keywords

• nonn

Comments

A 3D variant of A000938.

Examples

			For n=3, for example, the 49 collinear triples have coordinates (sorting according to the base-n representation of numbers from 0 to n^3-1):
[0, 0, 0], [1, 0, 0], [2, 0, 0]
[0, 0, 0], [0, 1, 0], [0, 2, 0]
[0, 0, 0], [1, 1, 0], [2, 2, 0]
[0, 0, 0], [0, 0, 1], [0, 0, 2]
[0, 0, 0], [1, 0, 1], [2, 0, 2]
[0, 0, 0], [0, 1, 1], [0, 2, 2]
[0, 0, 0], [1, 1, 1], [2, 2, 2]
[1, 0, 0], [1, 1, 0], [1, 2, 0]
[1, 0, 0], [1, 0, 1], [1, 0, 2]
[1, 0, 0], [1, 1, 1], [1, 2, 2]
[2, 0, 0], [1, 1, 0], [0, 2, 0]
[2, 0, 0], [2, 1, 0], [2, 2, 0]
[2, 0, 0], [1, 0, 1], [0, 0, 2]
[2, 0, 0], [2, 0, 1], [2, 0, 2]
[2, 0, 0], [1, 1, 1], [0, 2, 2]
[2, 0, 0], [2, 1, 1], [2, 2, 2]
[0, 1, 0], [1, 1, 0], [2, 1, 0]
[0, 1, 0], [0, 1, 1], [0, 1, 2]
[0, 1, 0], [1, 1, 1], [2, 1, 2]
[1, 1, 0], [1, 1, 1], [1, 1, 2]
[2, 1, 0], [1, 1, 1], [0, 1, 2]
[2, 1, 0], [2, 1, 1], [2, 1, 2]
[0, 2, 0], [1, 2, 0], [2, 2, 0]
[0, 2, 0], [0, 1, 1], [0, 0, 2]
[0, 2, 0], [1, 1, 1], [2, 0, 2]
[0, 2, 0], [0, 2, 1], [0, 2, 2]
[0, 2, 0], [1, 2, 1], [2, 2, 2]
[1, 2, 0], [1, 1, 1], [1, 0, 2]
[1, 2, 0], [1, 2, 1], [1, 2, 2]
[2, 2, 0], [1, 1, 1], [0, 0, 2]
[2, 2, 0], [2, 1, 1], [2, 0, 2]
[2, 2, 0], [1, 2, 1], [0, 2, 2]
[2, 2, 0], [2, 2, 1], [2, 2, 2]
[0, 0, 1], [1, 0, 1], [2, 0, 1]
[0, 0, 1], [0, 1, 1], [0, 2, 1]
[0, 0, 1], [1, 1, 1], [2, 2, 1]
[1, 0, 1], [1, 1, 1], [1, 2, 1]
[2, 0, 1], [1, 1, 1], [0, 2, 1]
[2, 0, 1], [2, 1, 1], [2, 2, 1]
[0, 1, 1], [1, 1, 1], [2, 1, 1]
[0, 2, 1], [1, 2, 1], [2, 2, 1]
[0, 0, 2], [1, 0, 2], [2, 0, 2]
[0, 0, 2], [0, 1, 2], [0, 2, 2]
[0, 0, 2], [1, 1, 2], [2, 2, 2]
[1, 0, 2], [1, 1, 2], [1, 2, 2]
[2, 0, 2], [1, 1, 2], [0, 2, 2]
[2, 0, 2], [2, 1, 2], [2, 2, 2]
[0, 1, 2], [1, 1, 2], [2, 1, 2]
[0, 2, 2], [1, 2, 2], [2, 2, 2]
		

Links

• R. H. Hardin, Table of n, a(n) for n = 1..60
• Hanno Lefmann, No l Grid-Points in spaces of small dimension, Lecture Notes in Comp. Sci. 5034 (2008) 259-270 [Provides motivation]
• Attilo Por and David R. Wood, No-Three-in-Line-in-3D, Algorithmica 47 (4) (2007) 481-488, [Provides motivation]
• Wikipedia, No-three-in-line problem.

Crossrefs

Cf. A178256-A178298, A178351-A178353.

Programs

Maple

# return true if xtrip1, xtrip2 and xtrip3 are three collinear points in 3D
iscolin := proc(xtrip1,xtrip2,xtrip3)
local diff21x, diff21y, diff21z, diff31x, diff31y, diff31z ;
# build the difference vectors diff2=xtrip2-xtrip1 and diff3=xtrip3-xtrip1
# and test whether diff2=t*diff3 with some parameter t
diff21x := xtrip2[1]-xtrip1[1] ;
diff21y := xtrip2[2]-xtrip1[2] ;
diff21z := xtrip2[3]-xtrip1[3] ;
diff31x := xtrip3[1]-xtrip1[1] ;
diff31y := xtrip3[2]-xtrip1[2] ;
diff31z := xtrip3[3]-xtrip1[3] ;
if xtrip1 = xtrip2 or xtrip2 = xtrip3 or xtrip1 = xtrip3 then
error("degen triple") ;
end if ;
# is diff31[] = t * diff21[] ?
if diff21x = 0 then
if diff31x = 0 then
# both difference vectors in the y-z plane
if diff21y = 0 then
if diff31y = 0 then
# both diff vects on the z-axis
return true;
else
# one on the z-axis, the other not
return false;
end if;
else
if diff31y = 0 then
# one on the z-axis, the other one not
return false;
else
# general directions in the y-z plane
t := diff31y/diff21y ;
if t*diff21z = diff31z then
return true ;
else
return false;
end if;
end if;
end if;
else
# one diff vector in the y-z plane, the other not
return false;
end if;
else
if diff31x = 0 then
# one diff vector in the y-z plane, the other not
return false;
else
t := diff31x/diff21x ;
if t*diff21y = diff31y and t*diff21z = diff31z then
return true;
else
return false;
end if;
end if;
end if;
end proc:
# convert a number n=0,1,2,3,... into a triple [n1,n2,n3], all 0<=niA000938: the number of collinear triples in n X n X n
num3in := proc(n)
local a,ncub,nlin1,nlin2,xtrip2,xtrip3 ;
a := 0 ;
ncub := n^3 ;
# linearized index of first point
for nlin1 from 0 to ncub-1 do
xtrip1 := linidx(nlin1,n) ; # [x,y,z], 0<=x,y,z
				

Extensions

Terms a(7) onwards from R. H. Hardin, May 21 2010

Replaced an invalid reference by Wikipedia and converted others to URL's R. J. Mathar, Jun 21 2010