A122223 -id:A122223 - cp's OEIS frontend

A127399 Number of segments of the longest possible zigzag paths fitting into a circle of diameter 2 if the path with index n is constructed according to the rules of the "Snakes on a Plane" problem of Al Zimmermann's programming contest.

2, 6, 4, 6, 7, 7, 8, 11, 9, 11, 12, 14, 13, 17, 16, 19, 20, 20, 23, 23, 23, 27, 27, 28, 29

Offset: 2

Hugo Pfoertner, Jan 12 2007

The extension of the contest problem to larger sets of hinge angles was proposed by James R. Buddenhagen. A link to the contest rules is given in A127400. Results up to n=32 were found by Markus Sigg. Known lower bounds for the next terms are a(27)>=29, a(28)>=32, a(29)>=34, a(30)>=34, a(31)>=34, a(32)>=39.

Hugo Pfoertner, Visualization of longest zigzag paths fitting into circle of diameter 2.

Cf. A127400 [solutions for container diameter 3], A127401 [solutions for container diameter 4], A122223, A122224, A122226 [solutions for hinge angles excluded from contest].

A127400 Number of segments of the longest possible zigzag paths fitting into a circle of diameter 3 if the path with index n is constructed according to the rules of the "Snakes on a Plane" problem of Al Zimmermann's programming contest.

Original entry on oeis.org

6, 8, 17, 10, 20, 22, 27, 23, 34, 33, 51, 44, 52

Offset: 3

Hugo Pfoertner, Jan 12 2007

The problems corresponding to n=3,4,6 had been excluded from the contest.

a(16) >= 52. - Hugo Pfoertner, Jun 30 2021

Contest Organizers, Snakes on a plane.. Rules for the Fall 2006 round of Al Zimmermann's Programming Contests.
Contest Organizers, Al Zimmermann's Programming Contests - Snakes on a Plane
Hugo Pfoertner, Submitted Zigzag Paths Sorted by Problem Class. Contest results.
Hugo Pfoertner, Longest snake for n=13
Hugo Pfoertner, Longest snake for n=14
Hugo Pfoertner, Longest snake for n=15, first possible configuration.
Hugo Pfoertner, Longest snake for n=15, second possible configuration.
Hugo Pfoertner, Longest known snake for n=16, conjectured unique solution.

Cf. A127399 [solutions for container diameter 2], A127401 [solutions for container diameter 4], A122223, A122224, A122226 [solutions for hinge angles excluded from contest].

a(13)-a(15) and update of links from Hugo Pfoertner, Jul 02 2011

A127401 Number of segments of the longest possible zigzag paths fitting into a circle of diameter 4 if the path with index n is constructed according to the rules of the "Snakes on a Plane" problem of Al Zimmermann's programming contest.

Original entry on oeis.org

12, 14, 33, 19, 43, 44, 59, 50

Offset: 3

Hugo Pfoertner, Jan 12 2007

Links to the contest rules and to visualizations of the results are given in A127400. Known lower bounds for the next terms are a(10)>=50, a(11)>=77, a(12)>=71. [updated by Hugo Pfoertner, May 21 2011]

Hugo Pfoertner, Data supporting a(10)=50, October 2020.

Cf. A127399 [solutions for container diameter 2], A127400 [solutions for container diameter 3], A122223, A122224, A122226 [solutions for hinge angles excluded from contest].

a(10) from Hugo Pfoertner, Nov 01 2020

A122224 Length of the longest possible self avoiding path on the 2-dimensional square lattice such that the path fits into a circle of diameter n.

Original entry on oeis.org

1, 4, 8, 14, 21, 32, 40

Offset: 2

Hugo Pfoertner, Sep 25 2006

The path may be open or closed. For larger n several solutions with the same number of segments exist.

It is conjectured that a(n) >= A123690(n)-1, i.e., that it is always possible to find a path visiting all grid points covered by a circle, irrespective of the position of its center. - Hugo Pfoertner, Mar 02 2018

Hugo Pfoertner, Examples of compact self avoiding paths on a square lattice.

Cf. A122223, A122226, A123690.

A346123 Numbers m such that no self-avoiding walk of length m + 1 on the honeycomb net fits into the smallest circle that can enclose a walk of length m.

Original entry on oeis.org

1, 2, 6, 7, 10, 12, 13, 14, 15, 16, 23, 24, 25, 27, 28, 30, 33, 36, 37, 38, 42, 43, 46, 53, 54, 55, 56, 58, 59, 62

Offset: 1

Hugo Pfoertner, Jul 05 2021

The segments of the walk can make relative turns of +- 60 degrees. The walks may be open or closed.

			Illustration of initial terms:
                               %%% %%% %%%
                           %                %
                         %                    %
      %  %              %                     /%
   %        %          %      a(2) = 2       /  %
  %__________%        %                     /    %
  %   L = 1  %       %                     /      %
   %  D = 1 %        %   L = 2, D = 1.732 /       %
      %  %           %                   /        %
                      %                 / Pi/3   %
    a(1) = 1           %-------------- .  .  . .%
                        %                      %
                          %                  %
                              %%% %%% %%%
.
           %%% %%%% %%%                         %%% %%%% %%%
        %                %                   %                %
      %                    %               %                  \ %
     %                      %             %                    \ %
    %                        %           %                      \ %
   %                          %         %                        \ %
  %                            %       %                          \ %
  %.      L = 3, D = 2.00     .%       %.      L = 4, D = 2.00     .%
  % \                        / %       % \                        / %
   % \                      / %         % \                      / %
    % \                    / %           % \                    / %
     % \                  / %             % \                  / %
       % ---------------- %                 % ---------------- %
           %%% %%% %%%                          %%% %%% %%%
.
            %%% %%% %%%                          %%% %%% %%%
        % ______________ %                   % ______________ %
      %                  \ %               % /                \ %
     %                    \ %             % /                  \ %
    %                      \ %           % /                    \ %
   %                        \ %         % /       a(3) = 6       \ %
  %                          \ %       % /                        \ %
  %.      L = 5, D = 2.00     .%       %.      L = 6, D = 2.00     .%
  % \                        / %       % \                        / %
   % \                      / %         % \                      / %
    % \                    / %           % \                    / %
     % \                  / %             % \                  / %
       % ---------------- %                 % ---------------- %
           %%% %%%% %%%                         %%% %%%% %%%
.
The path of minimum diameter of length 7 requires an enclosing circle of D = 3.055, which is greater than the previous minimum diameter of D = 2.00 corresponding to a(3) = 6. No path of length 8 exists that fits into a circle of D = 3.055, thus a(4) = 7.
See link for illustrations of terms corresponding to diameters D <= 9.85.

Hugo Pfoertner, Examples of paths of maximum length.

Cf. A122223, A127399, A127400, A127401, A258206, A266925.

Cf. A346124-A346132 similar to this sequence with other sets of turning angles.

a(n+1) >= a(n) + 1 for n > 1; a(1) = 1.

A122226 Length of the longest possible self-avoiding path on the 2-dimensional triangular lattice such that the path fits into a circle of diameter n.

Original entry on oeis.org

1, 7, 10, 19, 24, 37, 48, 61

Offset: 1

Hugo Pfoertner, Sep 25 2006

The path may be open or closed. For larger n several solutions with the same number of segments exist.

It is conjectured that the sequence is identical with A125852 for all n>1. That means that it is always possible to find an Hamiltonian cycle on the maximum possible number of lattice points that can be covered by circular disks of diameter >=2. For the given additional terms it was easily possible to construct such closed paths by hand, using the lattice subset found by the exhaustive search for A125852. See the examples at the end of the linked pdf file a122226.pdf that were all generated without using a program. - Hugo Pfoertner, Jan 12 2007

Hugo Pfoertner, Examples of compact self avoiding paths on a triangular lattice.

Cf. A003215, A004016; A125852 gives upper bounds for a(n).

Cf. A122223, A122224.

a(7) and a(8) from Hugo Pfoertner, Dec 11 2006

A127406 Number of points in a 2-dimensional honeycomb net covered by a circular disk of diameter n if the center of the disk is chosen to maximize the number of net points covered by the disk.

Original entry on oeis.org

2, 6, 7, 13, 17, 25, 34, 42, 54, 64, 78, 90, 107, 126, 140, 163, 178, 204, 222, 246

Offset: 1

Hugo Pfoertner, Feb 08 2007

a(n)>= max(A127402(n),A127403(n),A127404(n)). a(n) is an upper limit for the number of path segments in A122223.

Hugo Pfoertner, Maximal number of points in the honeycomb lattice covered by circular disks. Illustrations.

Cf. A127402, A127403, A127404, A127405, A122223. The corresponding sequences for the square lattice and hexagonal lattice are A123690 and A125852, respectively.

A322831 Average path length to self-trapping, rounded to nearest integer, of self-avoiding two-dimensional random walks using unit steps and direction changes from the set Pi(2k/n - 1), k = 1..n-1.

Original entry on oeis.org

71, 71, 40, 77, 45, 51, 42, 56, 49, 51, 48, 54

Offset: 3

Hugo Pfoertner, Dec 27 2018

The cases n = 3, 4, and 6 correspond to the usual self-avoiding random walks on the honeycomb net, the square lattice, and the hexagonal lattice, respectively. The other cases n = 5, 7, ... are a generalization using self-avoiding rooted walks similar to those defined in A306175, A306177, ..., A306182. The walk is trapped if it cannot be continued without either hitting an already visited (lattice) point or crossing or touching any straight line connecting successively visited points on the path up to the current point.
The result 71 for n=4 was established in 1984 by Hemmer & Hemmer.
The sequence data are based on the following results of at least 10^9 simulated random walks for each n <= 12, with an uncertainty of +- 0.004 for the average walk length:
   n  length
71.132
70.760 (+-0.001)
40.375
77.150
45.297
51.150
42.049
56.189
48.523
51.486
47.9   (+-0.2)
53.9   (+-0.2)

S. Hemmer, P. C. Hemmer, An average self-avoiding random walk on the square lattice lasts 71 steps, J. Chem. Phys. 81, 584 (1984)
Hugo Pfoertner, Examples of self-trapping random walks.
Hugo Pfoertner, Probability density for the number of steps before trapping occurs, 2018.
Hugo Pfoertner, Results for the 2D Self-Trapping Random Walk.
Alexander Renner, Self avoiding walks and lattice polymers, Diplomarbeit, Universität Wien, December 1994.

Cf. A001668, A001411, A001334, A077482, A306175, A306177, A306178, A306179, A306180, A306181, A306182.

Cf. A122223, A122224, A122226, A127399, A127400, A127401, A300665, A323141, A323560, A323562, A323699.

cp's OEIS Frontend

A127399 Number of segments of the longest possible zigzag paths fitting into a circle of diameter 2 if the path with index n is constructed according to the rules of the "Snakes on a Plane" problem of Al Zimmermann's programming contest.

Views

Author

Keywords

Comments

Links

Crossrefs

A127400 Number of segments of the longest possible zigzag paths fitting into a circle of diameter 3 if the path with index n is constructed according to the rules of the "Snakes on a Plane" problem of Al Zimmermann's programming contest.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A127401 Number of segments of the longest possible zigzag paths fitting into a circle of diameter 4 if the path with index n is constructed according to the rules of the "Snakes on a Plane" problem of Al Zimmermann's programming contest.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A122224 Length of the longest possible self avoiding path on the 2-dimensional square lattice such that the path fits into a circle of diameter n.

Views

Author

Keywords

Comments

Links

Crossrefs

A346123 Numbers m such that no self-avoiding walk of length m + 1 on the honeycomb net fits into the smallest circle that can enclose a walk of length m.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A122226 Length of the longest possible self-avoiding path on the 2-dimensional triangular lattice such that the path fits into a circle of diameter n.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A127406 Number of points in a 2-dimensional honeycomb net covered by a circular disk of diameter n if the center of the disk is chosen to maximize the number of net points covered by the disk.

Views

Author

Keywords

Comments

Links

Crossrefs

A322831 Average path length to self-trapping, rounded to nearest integer, of self-avoiding two-dimensional random walks using unit steps and direction changes from the set Pi*(2*k/n - 1), k = 1..n-1.

Views

Author

Keywords

Comments

Links

Crossrefs

A322831 Average path length to self-trapping, rounded to nearest integer, of self-avoiding two-dimensional random walks using unit steps and direction changes from the set Pi(2k/n - 1), k = 1..n-1.