3D random walks

[Wouter Meeussen]

hi all,

the counting of non-intersecting random walks in 3D.

A tetrahedral grid has coordination number = 4, so each succesive step of a
random walk implies choosing between 3 possible continuations.
Such a set of choices can be written as a integer in 'ternary' notations :
11_dececimal = 2*3^0 + 0*3^1 + 1*3^2 = 102_ternary
Inversely, each integer can be written in ternary, and so a 3D-random walk
corresponds to it.
Random walks that self-intercept form a closed loop at that instant.
For which integers does the walk self-intercept?
That of course depends on the link that is made between the ternary digit
and the 3D step it generates.
The following tetrahedral latice linkage scheme is 'prominent':
 
steps={  {  1,  1, -1},
	 {  1, -1,  1},
	 { -1,  1,  1},
	 { -1, -1, -1},
	 {  1,  1,  1},
	 {  1, -1, -1},
	 { -1,  1, -1},
	 { -1, -1,  1}};
indices=
       {{            5, 6, 7   },
	{            5, 6,    8},
        {            5,    7, 8},
	{               6, 7, 8},
	{1, 2, 3               },
	{1, 2,    4,           },
	{1,    3, 4            },
	{   2, 3, 4            }};

the linkage works as follows:

following a step {1,1,-1}, the first (=1) in list "steps",
only steps 5, 6 and 8 are allowed. These are tabulated in row (1) of the
"indices". (Since step 8 is the reverse of step 1, it is not allowed).

Starting from coordinates {0,0,0}, we fix the direction of the first step as
being {1,1,-1). From there on, the choice between subsequent steps {5,6,7}
will be determined by the ternary representation of our input number.
Logic dictates that we should put its high order digit last:

in Mathematica 3.0 :
Reverse[IntegerDigits[   n   ,3]+1]
       128  ->  {3,1,3,2,2}

we add a "1" to transform digits "0,1,2" into choices "1,2,3".

Using this scheme, we find closed loops for n=

 
{286,312,390,443,468,521,599,625,677,703,755,781,782,807,833,858,859,885,936,
  937,938,963,1015,1016,1041,1119,1170,1171,1172,1197,1249,1250,1328,1329,
  1354,1404,1405,1406,1432,1483,1484,1510,1536,1562,1563,1588,1614,1666,1692,
  1717,1718,1744,1770,1796,1797,1848,1875,1876,1901,1926,1951,1952,1979,2030,
  2031,2057,2083,2109,2110,2135,2161,2213,2239,2264,2265,2291,2317,2320,2343,
  2344,2345,2346,2347,2348,2395,2421,2422,2423,2473,2498,2499,2572,2573,2574,
  2575,2576,2577,2578,2630,2655,2656,2657,2665,2708,2786,2808,2809,2810,2811,
  2812,2813,2814,2864,2880,2889,2890,2891,2942,2968,2969,2994,3020,3045,3046,
  3047,3048,3049,3050,3072,3075,3123,3124,3125,3150,3202,3203,3228,3306,3357,
  3358,3359,3384,3436,3437,3510,3511,3512,3513,3514,3515,3516,3541,3591,3592,
  3593,3600,3619,3670,3671,3697,3720,3723,3747,3748,3749,3750,3751,3752,3775,
  3801,3853,3879,3896,3904,3905,3931,3957,3960,3983,3984,3985,3986,3987,3988,
  3989, ... }

Question :
        Is this a bona-fide "informative" integer sequence?
        Any suggestions? 

wouter.

****************************************************************************
Mma 3.0 program :

out={};
Do[  If[walk[Reverse[IntegerDigits[k,3]+1]],Print[k];
     AppendTo[out,k]],{k,1,4000}];out



walk[vec_]:=Module[{},
		la=wa={0,0,0};len=Length[vec];old=1;bump=False;
		i=1;
		While[!bump &&i<= len ,
                   la=la+step[[new=idx[[old,vec[[i]]   ]];  
                   If[FreeQ[wa,la],bump=True];
		   wa={wa,la };   old=new;
        	i++];(* Partition[Flatten[wa],3] *);
                bump ]

********************************************************************************










Dr. Wouter L. J. MEEUSSEN
w.meeussen.vdmcc at vandemoortele.be
eu000949 at pophost.eunet.be