Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.
%I #39 Dec 28 2022 01:54:33
%S 1,3,13
%N 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.
%C A generalization of the well-known "Nine Dots Problem".
%C 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).
%C A (trivial) lower bound is given by B(n):= (n^n - 1)/(n - 1). - _Marco Ripà_, Aug 25 2020
%H Roberto Rinaldi and Marco Ripà, <a href="https://arxiv.org/abs/2212.11216">Optimal cycles enclosing all the nodes of a k-dimensional hypercube</a>, arXiv:2212.11216 [math.CO], 2022.
%H Marco Ripà, <a href="/A225227/a225227.pdf">The Rectangular Spiral Solution for the n1 X n2 X ... X nk Points Problem</a>
%H Marco Ripà, <a href="http://nntdm.net/volume-20-2014/number-1/59-71/">The rectangular spiral or the n1 X n2 X ... X nk Points Problem</a>, Notes on Number Theory and Discrete Mathematics, 2014, 20(1), 59-71.
%H Marco Ripà, <a href="https://www.researchgate.net/publication/343050221_Solving_the_106_years_old_3k_Points_Problem_with_the_Clockwise-algorithm">Solving the 106 years old 3^k Points Problem with the Clockwise-algorithm</a>, ResearchGate, 2020 (DOI: 10.13140/RG.2.2.34972.92802).
%H Marco Ripà, <a href="https://www.researchgate.net/publication/342331014_Solving_the_n_1_n_2_n_3_Points_Problem_for_n_3_6">Solving the n_1 <= n_2 <= n_3 Points Problem for n_3 < 6</a>, ResearchGate, 2020 (DOI: 10.13140/RG.2.2.12199.57769/1).
%H Marco Ripà, <a href="https://ejournal2.undip.ac.id/index.php/jfma/article/view/12053">General uncrossing covering paths inside the Axis-Aligned Bounding Box</a>, Journal of Fundamental Mathematics and Applications, 2021, 4(2), 154-166.
%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Thinking_outside_the_box#Nine_dots_puzzle">Nine dots puzzle</a>
%e 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.
%Y Cf. A058992, A225227, A261547.
%K nonn,more,hard,bref
%O 1,2
%A _Marco Ripà_, Aug 20 2018
%E a(3) corrected by _Marco Ripà_, Aug 25 2020