login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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
1, 3, 14 (list; graph; refs; listen; history; text; internal format)
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).

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), 59-71.

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 21 08:47 EDT 2019. Contains 328292 sequences. (Running on oeis4.)