login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A157882 Number of collinear point-triples in the n X n X n cube. 40
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,3

COMMENTS

A 3D variant of A000938.

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.

EXAMPLE

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]

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<=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 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<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:

CROSSREFS

Cf. A178256-A178298, A178351-A178353.

Sequence in context: A017606 A206248 A100690 * A168572 A063874 A063132

Adjacent sequences:  A157879 A157880 A157881 * A157883 A157884 A157885

KEYWORD

nonn

AUTHOR

R. J. Mathar, May 21 2010

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified June 25 06:13 EDT 2017. Contains 288709 sequences.