A337519 - OEIS

The OEIS is supported by the many generous donors to the OEIS Foundation.

A337519

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

1

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

(list; graph; refs; listen; history; text; internal format)

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.

MATHEMATICA

LinearRecurrence[{2, 0, -2, 1}, {4, 15, 28, 47}, 80] (* Harvey P. Dale, Jan 09 2025 *)

CROSSREFS

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