A318165 The n^n dots problem: minimal number of straight lines (connected at their endpoints) required to pass through n^n dots arranged in an n X n X ... X n grid.

1, 3, 13

Offset

1,2

Comments

A generalization of the well-known "Nine Dots Problem".

For any n > 3, an upper bound for this problem is given by U(n) := (t + 1)*n^(n - 3) - 1, where "t" is the best known solution for the corresponding n X n X n case, and (for any n > 5) t = floor((3/2)*n^2) - floor((n - 1)/4) + floor((n + 1)/4) - floor((n - 2)/4) + floor(n/2) + n - 2 (e.g., U(4) = 95, since 23 is the current upper bound for the 4 X 4 X 4 problem). In particular, it is easily possible to prove the existence of an Hamiltonian path without self crossing such that U(4) = 95 (in fact, an Hamiltonian path with link-length 23 for the 4 X 4 X 4 problem was explicitly shown in June 2020).

A (trivial) lower bound is given by B(n):= (n^n - 1)/(n - 1). - Marco Ripà, Aug 25 2020

Links

Table of n, a(n) for n=1..3.

Roberto Rinaldi and Marco Ripà, Optimal cycles enclosing all the nodes of a k-dimensional hypercube, arXiv:2212.11216 [math.CO], 2022.

Marco Ripà, The Rectangular Spiral Solution for the n1 X n2 X ... X nk Points Problem

Marco Ripà, The rectangular spiral or the n1 X n2 X ... X nk Points Problem, Notes on Number Theory and Discrete Mathematics, 2014, 20(1), 59-71.

Marco Ripà, Solving the 106 years old 3^k Points Problem with the Clockwise-algorithm, ResearchGate, 2020 (DOI: 10.13140/RG.2.2.34972.92802).

Marco Ripà, Solving the n_1 <= n_2 <= n_3 Points Problem for n_3 < 6, ResearchGate, 2020 (DOI: 10.13140/RG.2.2.12199.57769/1).

Marco Ripà, General uncrossing covering paths inside the Axis-Aligned Bounding Box, Journal of Fundamental Mathematics and Applications, 2021, 4(2), 154-166.

Wikipedia, Nine dots puzzle

Example

For n = 3, a(3) = 13. You cannot touch (the centers of) the 3 X 3 X 3 dots using fewer than 13 straight lines, following the "Nine Dots Puzzle" basic rules.

Crossrefs

Cf. A058992, A225227, A261547.

Sequence in context: A239891 A226129 A167368 * A215240 A068697 A010258

Adjacent sequences: A318162 A318163 A318164 * A318166 A318167 A318168

Keyword

nonn,more,hard,bref

Author

Marco Ripà, Aug 20 2018

Extensions

a(3) corrected by Marco Ripà, Aug 25 2020

Status

approved