cp's OEIS Frontend

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

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