

A318165


The n^n dots problem (n times n): 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.


2




OFFSET

1,2


COMMENTS

A generalization of the wellknown "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).
A lower bound is given by B(n):= 1 + ceiling((n^n + (1/2)*n^3  3*n^2 + 5*n  4)/(n  1)) (e.g., B(4) = 87).


LINKS

Table of n, a(n) for n=1..3.
M. Ripà, nxnx...xn Dots Puzzle
M. Ripà, The Rectangular Spiral Solution for the n1 X n2 X ... X nk Points Problem
M. Ripà, The rectangular spiral or the n1 X n2 X ... X nk Points Problem, Notes on Number Theory and Discrete Mathematics, 2014, 20(1), 5971.
Marco Ripà, The n X n X n Points Problem Optimal Solution
Wikipedia, Nine dots puzzle


EXAMPLE

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


CROSSREFS

Cf. A058992, A225227, A261547.
Sequence in context: A174211 A264611 A157323 * A016549 A147584 A163357
Adjacent sequences: A318162 A318163 A318164 * A318166 A318167 A318168


KEYWORD

nonn,more,hard,bref


AUTHOR

Marco Ripà, Aug 20 2018


STATUS

approved



