A337519 Length of the shortest walk in an n X n grid graph that starts in one corner and visits every edge.

4, 15, 28, 47, 68, 95, 124, 159, 196, 239, 284, 335, 388, 447, 508, 575, 644, 719, 796, 879, 964, 1055, 1148, 1247, 1348, 1455, 1564, 1679, 1796, 1919, 2044, 2175, 2308, 2447, 2588, 2735, 2884, 3039, 3196, 3359, 3524, 3695, 3868, 4047, 4228, 4415, 4604, 4799, 4996

Offset

2,1

Comments

Nodes and edges can be revisited.

Links

Table of n, a(n) for n=2..50.

Dmitry Kamenetsky, A robot visiting every edge of a 3x3 grid, Puzzling StackExchange, August 2020.

Dmitry Kamenetsky, A robot visiting every edge of a 4x4 grid, Puzzling StackExchange, August 2020.

Dmitry Kamenetsky, Best known solutions for n <= 11.

Chris Staecker, MA 15: Minimum duplication circuits & Hamilton circuits, YouTube, May 2020.

Wikipedia, Eulerian Path.

Wikipedia, Route inspection problem.

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

Formula

When n is even, a(n) = A332044(n) = 2*n^2 - 4, otherwise a(n) = A332044(n) - 1 = 2*n^2 - 3.

From Stefano Spezia, Sep 18 2020: (Start)

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

a(n) = 2*a(n-1) - 2*a(n-3) + a(n-4) for n > 5. (End)

Example

See examples in links.

Crossrefs

Cf. A332044.

Sequence in context: A030553 A304567 A154493 * A031012 A349428 A188075

Adjacent sequences: A337516 A337517 A337518 * A337520 A337521 A337522

Keyword

nonn,easy

Author

Dmitry Kamenetsky, Aug 30 2020

Extensions

More terms from Stefano Spezia, Sep 18 2020

Status

approved