# [seqfan] 3D version of A000938: 3-in-line inside the nXnXn cube

Richard Mathar mathar at strw.leidenuniv.nl
Fri May 21 14:46:47 CEST 2010

```What is the 3D variant of A000938?
This should count the number of collinear point-triples in the n X n X n cube (i.d.,
in the simple cubic lattice). By scanning the binomial(n^3,3)
triples of distinct points in the cube (which is C(n^3,3) = 2925, 41664, 317750,...for n>=3),
I guess this starts (offset n=3): 49,376,1858,5696 (? to be confirmed)

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]

As a motivation see for example

Hanno Lefmann, No l Grid-Points in spaces of small dimension, Lecture Notes in Comp. Sci. , 5034 (2008) 259-270
http://dx.doi.org/10.1007/978-3-540-68880-8

Attilo Por, David R. Wood, No-Three-in-Line-in-3D, Algorithmica 47 (4) (2007) 481-488
http://dx.doi.org/10.1007/s00453-006-0158-9

Reid Andersen, Fan Chung, Linyuan Lu, No-Three-in-Line-in-3D Aglorithmica 47 (4) (2007) 379-497
http://dx.doi.org/10.1007/s00453-006-0160-2

# 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<=ni<sid
linidx := proc(n,sid)
local tr ;
tr := convert(n,base,sid) ;
while nops(tr) < 3 do
tr := [op(tr),0] ;
end do:
tr ;
end proc:

# 3D variant of A000938: the number of collinear triples in n-by-n-by-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<n
# linearized index of second point
for nlin2 from nlin1+1 to ncub-1 do
xtrip2 := linidx(nlin2,n) ; # [x,y,z], 0<=x,y,z<n
# linearized index of third point
for nlin3 from nlin2+1 to ncub-1 do
xtrip3 := linidx(nlin3,n) ; # [x,y,z], 0<=x,y,z<n
# count one more if collinear
if iscolin(xtrip1,xtrip2,xtrip3) then
a := a+1 ;
end if;
end do:
end do;
end do:
a ;
end proc:

for n from 3 do
print(n,num3in(n)) ;
end do:

```