%I #20 Jul 25 2020 09:49:48
%S 1,4,12,36,108,324,972,2876,8364,24124,69116,196916,559604,1585764,
%T 4495740,12714796,35654620,99686708,278880060,781504972,2180418716,
%U 6079373324,16857930068,46773551052,129562831140,358157148332
%N Number of self-avoiding walks on a 2-dimensional square lattice where the walk consists of steps with incrementing lengths equal to the prime numbers, from 2 to prime(n).
%C The first time a collision with a previous step can occur is for n = 7, i.e., a walk with steps of length 2,3,5,7,11,13,17. If we consider only walks starting with one or more steps to the right followed by an upward step then a collision can occur in five ways. These are 2R->3U->5U->7U->11R->13D->17L, 2R->3U->5U->7U->11L->13D->17R, 2R->3U->5R->7R->11U->13L->17D, 2R->3U->5R->7R->11D->13L->17U, 2R->3R->5R->7R->11U->13L->17D, where the number is the step length and R,L,U,D are directions right,left,up and down on the grid. Requiring seven steps before a collision can occur is in contrast to the walk where the steps' lengths increment by 1, see A334877, which requires only six steps.
%H A. J. Guttmann, <a href="http://dx.doi.org/10.1088/0305-4470/20/7/029">On the critical behavior of self-avoiding walks</a>, J. Phys. A 20 (1987), 1839-1854.
%H A. J. Guttmann and A. R. Conway, <a href="http://dx.doi.org/10.1007/PL00013842">Self-Avoiding Walks and Polygons</a>, Annals of Combinatorics 5 (2001) 319-345.
%e a(1) = 4. These are the four ways one can step away from the origin on a 2D square lattice.
%e a(2) = 12. These consist of the two following walks:
%e .
%e *
%e |
%e .
%e | 3 2 3
%e . *---.---*---.---.---*
%e |
%e *---.---*
%e 2
%e .
%e The first walk can be taken in eight different ways on the 2D square lattice, the second in four ways, giving a total of 12 walks.
%e a(7) = 2876. If we consider only walks starting with one or more steps to the right followed by an upward step, and ignoring collisions, then the total number of walks is 3^5+3^4+3^3+3^2+3^1+3^0 = 364. However, five of these are forbidden due to the collisions given in the comments, leaving 359 in total. These can be walked in eight different ways on the 2D grid. There are also the four straight walks along the axes. This gives a total of 359*8+4 = 2876 walks.
%Y Cf. A334877, A001411, A334602, A334720, A077482, A334720.
%K nonn,walk,more
%O 0,2
%A _Scott R. Shannon_, Jul 15 2020
|