A349895 Length of the longest self avoiding walk through a grid such that either x or y is changed by +1 or -1 in each step, and with 0 <= y, 0 <= x <= y, x + y <= n starting at (0,0) and terminating at (x,y) = (n,0).

0, 1, 2, 5, 6, 9, 12, 17, 20, 27, 30, 39, 42, 51, 56, 67, 72, 85, 90, 105, 110, 125, 132, 149, 156, 175, 182, 203, 210, 231, 240, 263, 272, 297, 306, 333, 342, 369, 380, 409, 420, 451, 462, 495, 506, 539, 552, 587, 600, 637, 650, 689, 702, 741, 756, 797, 812

Offset

0,3

Comments

The number of reachable nodes in the grid is given by A002620(n+2).

This sequence is inspired by the "Cinnamon Stars" problem given in the link. In this sequence an additional restriction that the walk must terminate at (n,0) has been added.

Links

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

Die Mathe-Adventskalender, Cinnamon Stars

Index entries for linear recurrences with constant coefficients, signature (1,1,-1,0,0,0,0,1,-1,-1,1).

Formula

a(n) < A002620(n+2).

From Andrew Howroyd, Dec 18 2021: (Start)

a(2*n) = n*(n + 1); a(2*n-1) = n^2 + n - 1 - 2*floor((n+1)/4).

G.f.: x*(1 + x + 2*x^2 + 2*x^5 + 2*x^6 + x^8 - x^9)/((1 - x)^3*(1 + x)^2*(1 + x^2)*(1 + x^4)).

a(n) = a(n-1) + a(n-2) - a(n-3) + a(n-8) - a(n-9) - a(n-10) + a(n-11) for n >= 11. (End)

Example

a(5) = 9. An optimal path is illustrated below:
           o---o
           |   |
       o---o   o   o
       |       |
   o---o   o   o---o---o
.
For n<13, an optimal path can be constructed by moving in y direction as far as possible (also avoiding dead ends), then moving one step in positive x direction, and going back in the other y direction. For example, a(6) = 12:
            o
.
        o   o---o
            |   |
    o---o   o   o   o
    |   |   |   |
o---o   o---o   o---o---o
.
From Andrew Howroyd, Dec 18 2021: (Start)
For even n, if vertices are colored alternately black and white there will be (n+2)*(n+4)/8 black vertices and n*(n+2)/8 white vertices. Since the walk must alternate between the two colors, the maximum length of the walk is limited to n*(n+2)/4. An optimal construction for a(10) is shown below. Many other solutions exist, but they all have the property that every white vertex is visited.
                      x
.
                  x   o---x
                      |   |
              x---o   x   o   x
              |   |   |   |
          x   o   x   o   x   o---x
              |   |   |   |   |   |
      x---o   x   o   x   o   x   o   x
      |   |   |   |   |   |   |   |
  x---o   x---o   x---o   x---o   x---o---x
.
For odd n, there will be an equal number of both colors. However, there is an imbalance between left and right halves that must be mitigated. The optimal solution is to fill in along the dividing line as shown below for a(11) = 39. In the illustration, black vertices are marked with x and white with o. Notice that the connections across the dividing line are always between a black vertex on the left and a white on the right. Even with the central crossings placed there will be more black vertices than white on the left (and vice versa on the right). An optimal solution is one in which every white vertex on the left side and every black vertex on the right side is included in the walk.
                      x---o
                      |   |
                  x---o   x---o
                  |           |
              x---o   x---o   x---o
              |       |   |       |
          x   o   x---o   x---o---x   o
              |   |
      x---o   x   o   x---o   x---o   x---o
      |   |   |   |   |   |   |   |   |   |
  x---o   x---o   x---o   x---o   x---o   x---o
(End)

Prog

(PARI) a(n)=if(n%2, (n^2 + 4*n - 1)/4 - (n+3)\8*2, n*(n/2 + 1)/2) \\ Andrew Howroyd, Dec 18 2021

Crossrefs

Cf. A002620.

Sequence in context: A050487 A046962 A022486 * A267700 A161910 A151920

Adjacent sequences: A349892 A349893 A349894 * A349896 A349897 A349898

Keyword

easy,nonn,walk

Author

Paul Bischof, Dec 04 2021

Extensions

Terms a(17) and beyond from Andrew Howroyd, Dec 18 2021

Status

approved