A122224 -id:A122224 - 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

A123690 Number of points in a square lattice covered by a circle of diameter n if the center of the circle is chosen such that the circle covers the maximum possible number of lattice points.

Original entry on oeis.org

2, 5, 9, 14, 22, 32, 41, 52, 69, 81, 97, 116, 137, 157, 180, 208, 231, 258, 293, 319, 351, 384, 421, 457, 495, 540, 578, 623, 667, 716, 761, 812, 861, 914, 973, 1025, 1085, 1142, 1201, 1268, 1328, 1396, 1460, 1528, 1597, 1669, 1745, 1816, 1893, 1976, 2053

Offset: 1

Hugo Pfoertner, Oct 09 2006, Feb 11 2007

nonn

a(n) >= max(A053411(n), A053414(n), A053415(n)).

a(n) is an upper bound for the number of segments of a self avoiding path on the 2-dimensional square lattice such that the path fits into a circle of diameter n. A122224(n) <= a(n).

			a(1)=2: Circle with diameter 1 and center (0,0.5) covers 2 lattice points;
a(2)=5: Circle with diameter 2 and center (0,0) covers 5 lattice points;
a(3)=4: Circle with diameter 3 and center (0,0) covers 9 lattice points;
a(4)=14: Circle with diameter 4 and center (0.5,0.2) covers 14 lattice points.

Hugo Pfoertner, Maximum number of points in the square lattice covered by circular disks. Illustrations.

Cf. A123689, A053411, A053414, A053415, A122224, A295344, A291259, A346993, A346994, A346995.

The corresponding sequences for the hexagonal lattice and the honeycomb net are A125852 and A127406, respectively.

(* An exact program using the functions from A291259: *)
Clear[a]; a[n_] := Module[{points, pairc, expcent, innerpoints, cn=Ceiling[n], allpairs},
allpairs = Flatten[Table[{i, j}, {i, -cn, cn+1}, {j, -cn, cn+1}], 1];
points = Select[allpairs, candidatePointQ[#, n]&];
pairc = Select[Subsets[points, {2}], dd2@@#<=4n^2&];
expcent = explorativeCenters[pairc, n];
innerpoints = Count[allpairs, _?(innerPointQ[#, n]&)];
Max[Table[Count[points, _?(dd2[#, center]<=n^2&)], {center, expcent}]] + innerpoints];
Table[a[n/2], {n, 20}] (* Andrey Zabolotskiy, Feb 21 2018 *)

a(21)-a(40) originally conjectured by Jean-François Alcover confirmed and moved to Data and more terms added by Andrey Zabolotskiy, Feb 21 2018

A331968 Maximum number of unit squares of a snake-like polyomino in an n X n square box.

Original entry on oeis.org

1, 3, 7, 11, 17, 24, 33, 42, 53, 64, 77, 92, 107, 123, 142, 162, 182

Offset: 1

Alain Goupil, Feb 02 2020

These are similar to the snake-in-the-box problem for the hypercube Q_n (See A099155).
The number of solutions is given by A331986(n).
Equivalently, a(n) is the maximum number of vertices in a path without chords in the n X n grid graph. A path without chords is an induced subgraph that is a path.
These numbers are part of the result of a computer program that counts the snake-like polyominoes in a rectangle of given size b X h by their length.
a(16) >= 161.

			For n=4, the maximum length of a snake-like polyomino that fits in a square of side 4 is 11 and there are 84 such snakes.
Maximum-length snakes for n = 1 to 4 are shown below.
   X    X X    X X X    X X X X
        X      X   X    X     X
               X   X    X     X
                        X   X X

Nikolai Beluhov, Snake paths in king and knight graphs, arXiv:2301.01152 [math.CO], 2023.
Alain Goupil, Illustration of initial terms
Eric Weisstein's World of Mathematics, Grid Graph

Main diagonal of A360917.

Cf. A099155, A047838, A122224, A331986, A332920, A332921, A357357, A357359.

a(n) >= A047838(n+1).
For n > 2: a(n) >= 2*floor(n/3)*(2n-3*floor(n/3)-2)+5. - Elijah Beregovsky, May 11 2020
a(n) <= (2*n*(n+1)-1)/3. - Elijah Beregovsky, Nov 09 2020
a(n) = 2*n^2/3 + O(n) (Beluhov 2023). - Pontus von Brömssen, Jan 30 2023

a(15) from Andrew Howroyd, Feb 04 2020

a(16)-a(17) from Yi Yang, Oct 03 2022

A122223 Length of the longest possible self avoiding path on the 2-dimensional honeycomb net such that the path fits into a circle of diameter n.

Original entry on oeis.org

1, 6, 6, 12, 15, 23, 33, 42, 53, 62, 74, 90, 103

Offset: 1

Hugo Pfoertner, Sep 25 2006, Feb 11 2007

The path may be open or closed. For larger n several solutions with the same number of segments exist. An upper bound for the number of segments is given by A127406(n).

Hugo Pfoertner, Examples of compact self avoiding paths on a honeycomb net.

Cf. A122224, A122226, A127406.

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

A123689 Number of points in a square lattice covered by a circle of diameter n if the center of the circle is chosen such that the circle covers the minimum possible number of lattice points.

Original entry on oeis.org

0, 2, 4, 10, 16, 26, 32, 46, 60, 74, 88, 108, 124, 146, 172, 194, 216, 248, 276, 308

Offset: 1

Hugo Pfoertner, Oct 09 2006

a(n)<=min(A053411(n),A053414(n),A053415(n)).

Using brute force computation and a step size of 1/1000 (though 1/200 suffices), the [conjectured] terms a(21) to a(40) would be: 332, 374, 408, 438, 484, 522, 560, 608, 648, 698, 740, 794, 846, 894, 952, 1006, 1060, 1124, 1184, 1248. - Jean-François Alcover, Jan 08 2018

			a(1)=0: Circle with diameter 1 with center (0.5,0.5) covers no lattice points; a(2)=2: Circle with diameter 2 with center (0,eps) covers 2 lattice points;
a(3)=4: Circle with diameter 3 with center (0.5,0.5) covers 4 lattice points.

Hugo Pfoertner, Minimal number of points in the square lattice covered by circular disks. Illustrations.

Cf. A123690, A053411, A053414, A053415, A122224, A291259.

The corresponding sequences for the hexagonal lattice and the honeycomb net are A125851 and A127405, respectively.

dx = 1/200; y0 = 0; (* To speed up computation, the step size dx is experimentally adjusted and the circle center is taken on the x-axis. *)
cnt[pts_, ctr_, r_] := Count[pts, pt_ /; Norm[pt - ctr] <= r];
a[n_] := Module[{r, pts, innerCnt, an, center}, r = n/2; pts = Select[ Flatten[ Table[{x, y}, {x, -r - 1, r + 1}, {y, -r - 1, r + 1}], 1], r - 1 <= Norm[#] <= r + 1 &]; innerCnt = Sum[If[Norm[{x, y}] < r - 1, 1, 0], {x, -r - 1, r + 1}, {y, -r - 1, r + 1}]; {an, center} = Table[{innerCnt + cnt[pts, {x, y0}, r], {x, y0}}, {x, -1/2, 1/2, dx}] // Sort // First; Print["a(", n, ") = ", an, ", center = ", center // InputForm]; an];
Table[a[n], {n, 1, 20}] (* Jean-François Alcover, Jan 08 2018 *)

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.

A346124 Numbers m such that no self-avoiding walk of length m + 1 on the square lattice fits into the smallest circle that can enclose a walk of length m.

Original entry on oeis.org

1, 4, 6, 8, 12, 14, 15, 16, 18, 20, 21, 23, 24, 25, 26, 27, 28, 32, 34, 36, 38, 44, 46, 48, 52, 56, 58, 60

Offset: 1

Hugo Pfoertner and Markus Sigg, Jul 30 2021

Closed walks are allowed.

			See link for illustrations of terms corresponding to diameters D < 8.5.

Hugo Pfoertner, Examples of paths of maximum length.

The squared radii of the enclosing circles are a subset of A192493/A192494.
Cf. A037245, A122224, A127399, A127400, A127401, A266549, A316194, A346993, A346994, A346995.
Cf. A346123-A346132 similar to this sequence with other sets of turning angles.

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

A123690 Number of points in a square lattice covered by a circle of diameter n if the center of the circle is chosen such that the circle covers the maximum possible number of lattice points.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A331968 Maximum number of unit squares of a snake-like polyomino in an n X n square box.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A122223 Length of the longest possible self avoiding path on the 2-dimensional honeycomb net such that the path fits into a circle of diameter n.

Views

Author

Keywords

Comments

Links

Crossrefs

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

A123689 Number of points in a square lattice covered by a circle of diameter n if the center of the circle is chosen such that the circle covers the minimum possible number of lattice points.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

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

A346124 Numbers m such that no self-avoiding walk of length m + 1 on the square lattice fits into the smallest circle that can enclose a walk of length m.

Views

Author

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.