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
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 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
KEYWORD
nonn,more,hard,bref
AUTHOR
Marco Ripà, Aug 20 2018
EXTENSIONS
a(3) corrected by Marco Ripà, Aug 25 2020
STATUS
approved