A336262 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).

1, 4, 12, 36, 108, 324, 972, 2876, 8364, 24124, 69116, 196916, 559604, 1585764, 4495740, 12714796, 35654620, 99686708, 278880060, 781504972, 2180418716, 6079373324, 16857930068, 46773551052, 129562831140, 358157148332

Offset

0,2

Comments

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.

Links

Table of n, a(n) for n=0..25.

A. J. Guttmann, On the critical behavior of self-avoiding walks, J. Phys. A 20 (1987), 1839-1854.

A. J. Guttmann and A. R. Conway, Self-Avoiding Walks and Polygons, Annals of Combinatorics 5 (2001) 319-345.

Example

a(1) = 4. These are the four ways one can step away from the origin on a 2D square lattice.
a(2) = 12. These consist of the two following walks:
.
        *
        |
        .
        | 3        2         3
        .      *---.---*---.---.---*
        |
*---.---*
     2
.
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.
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.

Crossrefs

Cf. A334877, A001411, A334602, A334720, A077482, A334720.

Sequence in context: A001394 A156946 A163877 * A164353 A347506 A164697

Adjacent sequences: A336259 A336260 A336261 * A336263 A336264 A336265

Keyword

nonn,walk,more

Author

Scott R. Shannon, Jul 15 2020

Status

approved