|
%I #14 Mar 31 2021 17:56:00
%S 0,0,49,376,1858,5696,16427,36992,78204,150672,277005,463624,776494,
%T 1212208,1845911,2749568,4023608,5654976,7915497,10730616,14487706,
%U 19290352,25343011,32580752,41959412,53240624,66913605,83330712
%N Number of collinear point-triples in the n X n X n cube.
%C A 3D variant of A000938.
%H R. H. Hardin, <a href="/A157882/b157882.txt">Table of n, a(n) for n = 1..60</a>
%H Hanno Lefmann, <a href="http://dx.doi.org/10.1007/978-3-540-68880-8_25">No l Grid-Points in spaces of small dimension</a>, Lecture Notes in Comp. Sci. 5034 (2008) 259-270 [Provides motivation]
%H Attilo Por and David R. Wood, <a href="http://dx.doi.org/10.1007/s00453-006-0158-9">No-Three-in-Line-in-3D</a>, Algorithmica 47 (4) (2007) 481-488, [Provides motivation]
%H Wikipedia, <a href="http://en.wikipedia.org/wiki/No-three-in-line_problem">No-three-in-line problem</a>.
%e 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):
%e [0, 0, 0], [1, 0, 0], [2, 0, 0]
%e [0, 0, 0], [0, 1, 0], [0, 2, 0]
%e [0, 0, 0], [1, 1, 0], [2, 2, 0]
%e [0, 0, 0], [0, 0, 1], [0, 0, 2]
%e [0, 0, 0], [1, 0, 1], [2, 0, 2]
%e [0, 0, 0], [0, 1, 1], [0, 2, 2]
%e [0, 0, 0], [1, 1, 1], [2, 2, 2]
%e [1, 0, 0], [1, 1, 0], [1, 2, 0]
%e [1, 0, 0], [1, 0, 1], [1, 0, 2]
%e [1, 0, 0], [1, 1, 1], [1, 2, 2]
%e [2, 0, 0], [1, 1, 0], [0, 2, 0]
%e [2, 0, 0], [2, 1, 0], [2, 2, 0]
%e [2, 0, 0], [1, 0, 1], [0, 0, 2]
%e [2, 0, 0], [2, 0, 1], [2, 0, 2]
%e [2, 0, 0], [1, 1, 1], [0, 2, 2]
%e [2, 0, 0], [2, 1, 1], [2, 2, 2]
%e [0, 1, 0], [1, 1, 0], [2, 1, 0]
%e [0, 1, 0], [0, 1, 1], [0, 1, 2]
%e [0, 1, 0], [1, 1, 1], [2, 1, 2]
%e [1, 1, 0], [1, 1, 1], [1, 1, 2]
%e [2, 1, 0], [1, 1, 1], [0, 1, 2]
%e [2, 1, 0], [2, 1, 1], [2, 1, 2]
%e [0, 2, 0], [1, 2, 0], [2, 2, 0]
%e [0, 2, 0], [0, 1, 1], [0, 0, 2]
%e [0, 2, 0], [1, 1, 1], [2, 0, 2]
%e [0, 2, 0], [0, 2, 1], [0, 2, 2]
%e [0, 2, 0], [1, 2, 1], [2, 2, 2]
%e [1, 2, 0], [1, 1, 1], [1, 0, 2]
%e [1, 2, 0], [1, 2, 1], [1, 2, 2]
%e [2, 2, 0], [1, 1, 1], [0, 0, 2]
%e [2, 2, 0], [2, 1, 1], [2, 0, 2]
%e [2, 2, 0], [1, 2, 1], [0, 2, 2]
%e [2, 2, 0], [2, 2, 1], [2, 2, 2]
%e [0, 0, 1], [1, 0, 1], [2, 0, 1]
%e [0, 0, 1], [0, 1, 1], [0, 2, 1]
%e [0, 0, 1], [1, 1, 1], [2, 2, 1]
%e [1, 0, 1], [1, 1, 1], [1, 2, 1]
%e [2, 0, 1], [1, 1, 1], [0, 2, 1]
%e [2, 0, 1], [2, 1, 1], [2, 2, 1]
%e [0, 1, 1], [1, 1, 1], [2, 1, 1]
%e [0, 2, 1], [1, 2, 1], [2, 2, 1]
%e [0, 0, 2], [1, 0, 2], [2, 0, 2]
%e [0, 0, 2], [0, 1, 2], [0, 2, 2]
%e [0, 0, 2], [1, 1, 2], [2, 2, 2]
%e [1, 0, 2], [1, 1, 2], [1, 2, 2]
%e [2, 0, 2], [1, 1, 2], [0, 2, 2]
%e [2, 0, 2], [2, 1, 2], [2, 2, 2]
%e [0, 1, 2], [1, 1, 2], [2, 1, 2]
%e [0, 2, 2], [1, 2, 2], [2, 2, 2]
%p # return true if xtrip1, xtrip2 and xtrip3 are three collinear points in 3D
%p iscolin := proc(xtrip1,xtrip2,xtrip3)
%p local diff21x, diff21y, diff21z, diff31x, diff31y, diff31z ;
%p # build the difference vectors diff2=xtrip2-xtrip1 and diff3=xtrip3-xtrip1
%p # and test whether diff2=t*diff3 with some parameter t
%p diff21x := xtrip2[1]-xtrip1[1] ;
%p diff21y := xtrip2[2]-xtrip1[2] ;
%p diff21z := xtrip2[3]-xtrip1[3] ;
%p diff31x := xtrip3[1]-xtrip1[1] ;
%p diff31y := xtrip3[2]-xtrip1[2] ;
%p diff31z := xtrip3[3]-xtrip1[3] ;
%p if xtrip1 = xtrip2 or xtrip2 = xtrip3 or xtrip1 = xtrip3 then
%p error("degen triple") ;
%p end if ;
%p # is diff31[] = t * diff21[] ?
%p if diff21x = 0 then
%p if diff31x = 0 then
%p # both difference vectors in the y-z plane
%p if diff21y = 0 then
%p if diff31y = 0 then
%p # both diff vects on the z-axis
%p return true;
%p else
%p # one on the z-axis, the other not
%p return false;
%p end if;
%p else
%p if diff31y = 0 then
%p # one on the z-axis, the other one not
%p return false;
%p else
%p # general directions in the y-z plane
%p t := diff31y/diff21y ;
%p if t*diff21z = diff31z then
%p return true ;
%p else
%p return false;
%p end if;
%p end if;
%p end if;
%p else
%p # one diff vector in the y-z plane, the other not
%p return false;
%p end if;
%p else
%p if diff31x = 0 then
%p # one diff vector in the y-z plane, the other not
%p return false;
%p else
%p t := diff31x/diff21x ;
%p if t*diff21y = diff31y and t*diff21z = diff31z then
%p return true;
%p else
%p return false;
%p end if;
%p end if;
%p end if;
%p end proc:
%p # convert a number n=0,1,2,3,... into a triple [n1,n2,n3], all 0<=ni<sid
%p linidx := proc(n,sid)
%p local tr ;
%p tr := convert(n,base,sid) ;
%p while nops(tr) < 3 do
%p tr := [op(tr),0] ;
%p end do:
%p tr ;
%p end proc:
%p # 3D variant of A000938: the number of collinear triples in n X n X n
%p num3in := proc(n)
%p local a,ncub,nlin1,nlin2,xtrip2,xtrip3 ;
%p a := 0 ;
%p ncub := n^3 ;
%p # linearized index of first point
%p for nlin1 from 0 to ncub-1 do
%p xtrip1 := linidx(nlin1,n) ; # [x,y,z], 0<=x,y,z<n
%p # linearized index of second point
%p for nlin2 from nlin1+1 to ncub-1 do
%p xtrip2 := linidx(nlin2,n) ; # [x,y,z], 0<=x,y,z<n
%p # linearized index of third point
%p for nlin3 from nlin2+1 to ncub-1 do
%p xtrip3 := linidx(nlin3,n) ; # [x,y,z], 0<=x,y,z<n
%p # count one more if collinear
%p if iscolin(xtrip1,xtrip2,xtrip3) then
%p a := a+1 ;
%p end if;
%p end do:
%p end do;
%p end do:
%p a ;
%p end proc:
%p for n from 3 do
%p print(n,num3in(n)) ;
%p end do:
%Y Cf. A178256-A178298, A178351-A178353.
%K nonn
%O 1,3
%A _R. J. Mathar_, May 21 2010
%E Terms a(7) onwards from _R. H. Hardin_, May 21 2010
%E Replaced an invalid reference by Wikipedia and converted others to URL's _R. J. Mathar_, Jun 21 2010
|
