A363755 -id:A363755 - cp's OEIS frontend

A225227 The n X n X n dots problem: minimal number of straight lines (connected at their endpoints) required to pass through n^3 dots arranged in an n X n X n grid, without exiting from the box [0, n] X [0, n] X [0, n].

1, 7, 13

Offset: 1

Marco Ripà, May 02 2013

A generalization of the well-known "Nine Dots Problem", where the regular axis-aligned bounding box (RAABB:=[0, n] X [0, n] X [0, n]) has been declared.
From Marco Ripà, Aug 10 2020: (Start)
In particular, if we loosen the constraint on the allowed AABB, covering paths characterized by a shorter link-length can be found, such as 5 <= a(2) <= 6, where the aforementioned upper bound has been discovered by Koki Goma in August 2021, providing the self-crossing covering path (0,0,0)-(2,2,0)-(1/2,1/2,3/2)-(2,-1,0)-(0,1,0)-(0,1,1)-(0,0,1).
Moreover, the above pattern suggests different uncrossing covering paths of the same link-length, such as (1,0,0)-(0,0,0)-(2,2,2)-(1/2,-1,1/2)-(-1/2,1,3/2)-(1,1,0)-(1,1,0) and also the (self-crossing) covering path (1,0,0)-(0,0,0)-(0,1,0)-(3/2,1,3/2)-(1/2,-1,1/2)-(-1/2,1,3/2)-(1,1,0) which is entirely contained inside a box of 1.5 X 2 X 2 units^3 but which does not match the RAABB. (End)

			For n = 2, a(2) = 7. You cannot touch the 8 vertices of a cube using fewer than 7 straight lines and without exiting from the box [0, 2] X [0, 2] X [0, 2], following the "Nine Dots Puzzle" basic rules.

Marco Ripà, Solving the n_1 <= n_2 <= n_3 Points Problem for n_3 < 6, ResearchGate, 2020.
Marco Ripà, Solving the 106 years old 3^k points problem with the clockwise-algorithm, Journal of Fundamental Mathematics and Applications, 2020, 3(2), 84-97.
Marco Ripà, General uncrossing covering paths inside the Axis-Aligned Bounding Box, Journal of Fundamental Mathematics and Applications, 2021, 4(2), 154-166.
Marco Ripà, General conjecture on the optimal covering trails in a k-dimensional cubic lattice, hal-03841209v3, 2023.
Wikipedia, Nine dots puzzle

Cf. A058992, A261547, A318165, A363755.

For any n >= 3, (n^3 - 1)/(n - 1) <= a(n) <= floor((3*n^2)/2) - floor((n - 1)/4) + floor((n + 1)/4) - floor((n + 2)/4) + floor(n/4) + n - 2. - Marco Ripà, Oct 25 2024

Entry revised by N. J. A. Sloane, May 02 2013

a(3) corrected by Marco Ripà, Jul 19 2020

A373537 Decimal expansion of the Euclidean length of the shortest minimum-link polygonal chains joining all the vertices of the cube [0,1]^3.

Original entry on oeis.org

1, 1, 1, 0, 5, 2, 5, 1, 1, 2, 3, 0, 6, 5, 3, 3, 1, 7, 9, 7, 3, 5, 9, 1, 7, 1, 1, 2, 1, 5, 2, 4, 1, 9, 5, 1, 2, 7, 9, 3, 9, 2, 0, 9, 8, 0, 9, 9, 1, 9, 1, 7, 3, 4, 3, 8, 5, 9, 0, 0, 5, 5, 1, 8, 2, 1, 6, 5, 5, 0, 6, 1, 1, 2, 7, 2, 8, 5, 2, 4, 2, 1, 8, 3, 1, 7, 3

Offset: 2

Marco Ripà, Jun 08 2024

It has been proved that it is not possible to join the 8 vertices of a cube with a polygonal chain that has fewer than 6 edges (see Links, Optimal cycles enclosing all the nodes of a k-dimensional hypercube, Theorem 2.2).
Here we consider the additional constraint of minimizing the total (Euclidean) length of the minimum-link polygonal chains (which consist of exactly 6 line segments connected at their endpoints) that join all the vertices of the cube [0,1] X [0,1] X [0,1].
A solution to the above-stated problem is provided by the 6-link polygonal chain (0,0,1)-(0,0,0)-(1+(x+2+sqrt(2))/(2*sqrt(2)(x+sqrt(2))),1+(x+2+sqrt(2))/(2*sqrt(2)(x+sqrt(2))),0)-(1/2,1/2,1+x/sqrt(2))-(- (x+2+sqrt(2))/(2*sqrt(2)(x+sqrt(2))),1+(x+2+sqrt(2))/(2*sqrt(2)(x+sqrt(2))),0)-(1,0,0)-(1,0,1), where x = (1/2)*sqrt((2/3)^(2/3)*((9+sqrt(177)))^(1/3) - 4*(2/(27+3*sqrt(177)))^(1/3)) + (1/2)*sqrt(4*(2/(27+3*sqrt(177)))^(1/3) - (2/3)^(2/3)*(9+sqrt(177))^(1/3) + 4*sqrt(2/((2/3)^(2/3)*(9+sqrt(177))^(1/3) - 4*(2/(27+3*sqrt(177)))^(1/3)))) = 1.597920933550032074764705350780465558827883608091828573735862154752648...
The total (Euclidean) length of the mentioned polygonal chain is about 11.105251123 and this value cannot be beaten by any other 6-link polygonal chain covering all the vertices belonging to the set {0,1} X {0,1} X {0,1} (a nice proof was posted on MathOverflow on June 5, 2024 by a new user, DR.LL, whose profile was subsequently deleted for unknown reasons).

			11.10525112306533179735917112152419512793920980991917343859...

Matematicamente.it, Problema di minimizzazione con un triangolo rettangoloe.
Math Overflow, Shortest polygonal chain with 6 edges visiting all the vertices of a cube.
Roberto Rinaldi and Marco Ripà, Optimal cycles enclosing all the nodes of a k-dimensional hypercube, arXiv:2212.11216 [math.CO], 2022.

Cf. A225227, A261547, A363755.

my(x=solve(x=1.5,1.7,4-8*x^2-4*x^4+x^8)); 2 + sqrt(2) + (sqrt(1 + 1/x^2) + 1/x) * (2 + sqrt(2)*x) \\ Hugo Pfoertner, Jun 10 2024

Equals 2*(1+1/sqrt(2)+((2+sqrt(2)*x)/2)*(1/x+sqrt(1+1/x^2))), where x = (1/2)*sqrt((2/3)^(2/3)*((9+sqrt(177)))^(1/3) - 4*(2/(27+3*sqrt(177)))^(1/3)) + (1/2)*sqrt(4*(2/(27+3*sqrt(177)))^(1/3) - (2/3)^(2/3)*(9+sqrt(177))^(1/3) + 4*sqrt(2/((2/3)^(2/3)*(9+sqrt(177))^(1/3) - 4*(2/(27+3*sqrt(177)))^(1/3)))) = 1.59792093355003207476470...

A374149 Decimal expansion of the minimum volume of an axis-aligned bounding box which includes the shortest minimum-link polygonal chain joining all the vertices of the cube {0,1}^3.

Original entry on oeis.org

5, 5, 4, 5, 0, 8, 4, 9, 7, 1, 8, 7, 4, 7, 3, 7, 1, 2, 0, 5, 1, 1, 4, 6, 7, 0, 8, 5, 9, 1, 4, 0, 9, 5, 2, 9, 4, 3, 0, 0, 7, 7, 2, 9, 4, 9, 5, 1, 4, 4, 0, 7, 1, 5, 5, 3, 3, 8, 6, 2, 1, 5, 5, 6, 7, 6, 3, 1, 5, 1, 1, 5, 7, 0, 4, 7, 2, 5, 6, 1, 2, 4, 2, 6, 8, 0, 1

Offset: 1

Marco Ripà, Jun 29 2024

It has been proved that it is not possible to join the 8 vertices of a cube with a polygonal chain that has fewer than 6 edges (see Links, Optimal cycles enclosing all the nodes of a k-dimensional hypercube, Theorem 2.2).
Here we are considering the additional constraint that asks to minimize the volume of the Axis-Aligned Bounding Box (AABB) including the above-mentioned optimal polygonal chain consisting of only 6 connected line segments and that joins all the vertices of the cube [0,1] X [0,1] X [0,1].
Given phi = (1+sqrt(5))/2, the well-known golden ratio (see A001622), a valid polygonal chain is (0, 1, 0)-(0, 0, 0)-((1+phi)/2, 0, (1+phi)/2)-(1/2, 1+phi, 1/2)-((1-phi)/2, 0, (1+phi)/2)-(1, 0, 0)-(1, 1, 0) (see Links, p. 164), and consequently the minimum volume AABB is [(1-phi)/2, (1+phi)/2] X [0, 1+phi] X [0, (1+phi)/2].
As noted by Hugo Pfoertner, the present sequence is also given by phi^5/2 (i.e., A244593/2).

			5.5450849718747371205114670859140952943...

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

Cf. A001622, A134944, A225227, A244593, A261547, A363755, A373537.

RealDigits[(11+5*Sqrt[5])/4, 10, 100][[1]]

Equals phi*(1+phi)*((1+phi)/2), where phi := (1+sqrt(5))/2 is the golden ratio.
Equals (11+5*sqrt(5))/4.
Equals phi^5/2.
Equals 10*A134944 + 3/2.

A374883 Decimal expansion of phi(2phi + 1) (i.e., (7 + 3*sqrt(5))/2), where phi is the golden ratio.

Original entry on oeis.org

6, 8, 5, 4, 1, 0, 1, 9, 6, 6, 2, 4, 9, 6, 8, 4, 5, 4, 4, 6, 1, 3, 7, 6, 0, 5, 0, 3, 0, 9, 6, 9, 1, 4, 3, 5, 3, 1, 6, 0, 9, 2, 7, 5, 3, 9, 4, 1, 7, 2, 8, 8, 5, 8, 6, 4, 0, 6, 3, 4, 5, 8, 6, 8, 1, 1, 5, 7, 8, 1, 3, 8, 8, 4, 5, 6, 7, 0, 7, 3, 4, 9, 1, 2, 1, 6, 2

Offset: 1

Marco Ripà, Jul 22 2024

The author conjectures that this is the minimum volume of an axis-aligned bounding box which includes the shortest minimum-link circuit joining all the vertices of the cube {0,1}^3 (i.e., the closed polygonal chains consisting of exactly 6 edges visiting all the points of the set {(0,0,0),(0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),(1,1,0),(1,1,1)}).
In detail, such a circuit of 6 links is given by (1/2,1+phi,1/2)-((1-phi)/2,0,(1+phi)/2)-((phi+1)/2,0, (1-phi)/2)-(1/2,1+phi,1/2)-((phi+1)/2,0,(phi+1)/2)-((1-phi)/2,0,(1-phi)/2(1/2,1+phi,1/2), where phi := (1+sqrt(5))/2 (see A001622).
Then, phi*(2*phi + 1) = phi^2*(phi + 1) since phi - 1 = 1/phi.

			6.8541019662496845446137605030969...

Alfred S. Posamentier, Math Charmers, Tantalizing Tidbits for the Mind, Prometheus Books, NY, 2003, pages 138-139.

Roberto Rinaldi and Marco Ripà, Optimal cycles enclosing all the nodes of a k-dimensional hypercube, arXiv:2212.11216 [math.CO], 2022.
Marco Ripà, General uncrossing covering paths inside the Axis-Aligned Bounding Box, Journal of Fundamental Mathematics and Applications, Volume 4, 2021, Number 2, Pages 154-166.

Cf. A001622, A090550, A104457, A134973, A205769, A225227, A261547, A363755, A373537, A374149, A374260.

RealDigits[3*GoldenRatio + 2, 10, 120][[1]] (* Amiram Eldar, Jul 23 2024 *)

Equals (7 + 3*sqrt(5))/2.
Equals phi^2*(phi + 1), where phi = (1 + sqrt(5))/2.
Equals A104457^2 = 2*A205769. - Hugo Pfoertner, Jul 22 2024
Equals A090550 + 1 = A134973 + 5. - Amiram Eldar, Jul 23 2024
Equals phi^4. - Stefano Spezia, May 28 2025

A374260 Decimal expansion of the Euclidean length of the shortest circuit covering all the vertices of the cube [0,1]^3.

Original entry on oeis.org

1, 5, 3, 8, 2, 0, 7, 5, 1, 2, 1, 3, 8, 4, 4, 7, 3, 4, 9, 7, 1, 1, 4, 9, 6, 4, 7, 9, 4, 6, 2, 8, 9, 9, 4, 0, 9, 8, 7, 3, 9, 0, 7, 5, 8, 6, 9, 0, 8, 4, 4, 5, 0, 7, 3, 0, 8, 2, 6, 7, 5, 0, 8, 8, 8, 3, 4, 9, 5, 4, 7, 2, 6, 8, 5, 3, 2, 8, 3, 4, 3, 5, 8, 9, 3, 3, 8

Offset: 2

Marco Ripà, Jul 01 2024

It has been proved that it is not possible to join the 8 vertices of a cube with a polygonal chain that has fewer than 6 edges (see Links, Optimal cycles enclosing all the nodes of a k-dimensional hypercube, Theorem 2.2). Thus, any circuit of 6 line segments covering all the vertices of a cube has the minimum link-length (by definition).
Here we consider the additional constraint of minimizing the total (Euclidean) length of the minimum-link circuit (which consists of exactly 6 line segments connected at their endpoints) that joins all the vertices of the cube [0,1] X [0,1] X [0,1].
Let x := (1/2)*sqrt((2/3)^(2/3)*((9+sqrt(177)))^(1/3) - 4*(2/(27+3*sqrt(177)))^(1/3)) + (1/2)*sqrt(4*(2/(27+3*sqrt(177)))^(1/3) - (2/3)^(2/3)*(9+sqrt(177))^(1/3) + 4*sqrt(2/((2/3)^(2/3)*(9+sqrt(177))^(1/3) - 4*(2/(27+3*sqrt(177)))^(1/3)))) = 1.597920933550032074764705350780465558827883608091828573735862154752648..., and then let c := 1+(x+2+sqrt(2))/(2*sqrt(2)*(x+sqrt(2))).
A solution to the above-stated problem is provided by the 6-link circuit (1/2, 1/2, 1+x/sqrt(2))-(c,c,0)-(-c,-c,0)-(1/2,1/2, 1+x/sqrt(2))-(-c,c,0)-(c,-c,0)-(1/2, 1/2, 1+x/sqrt(2)).
The total (Euclidean) length of the mentioned circuit is given by 4*((2+sqrt(2)*x)/2)*(1/x+sqrt(1+1/x^2)) = which is about 11.105251123 and this value cannot be beaten by any other 6-link circuit covering all the vertices belonging to the set {0,1} X {0,1} X {0,1}. This result follows by symmetry from the optimal polygonal chain described in the comments of A373537.

			15.382075121384473497114964794628994098739075869...

Matematicamente.it, Problema di minimizzazione con un triangolo rettangolo.
Roberto Rinaldi and Marco Ripà, Optimal cycles enclosing all the nodes of a k-dimensional hypercube, arXiv:2212.11216 [math.CO], 2022.

Cf. A225227, A261547, A363755, A373537.

my(x=solve(x=1.5, 1.7, 4-8*x^2-4*x^4+x^8)); 2*(sqrt(1 + 1/x^2) + 1/x)*(2 + x*sqrt(2)) \\ Hugo Pfoertner, Jul 01 2024

Equals 2*(2+sqrt(2)*x)*(1/x+sqrt(1+1/x^2)), where x = (1/2)*sqrt((2/3)^(2/3)*((9+sqrt(177)))^(1/3) - 4*(2/(27+3*sqrt(177)))^(1/3)) + (1/2)*sqrt(4*(2/(27+3*sqrt(177)))^(1/3) - (2/3)^(2/3)*(9+sqrt(177))^(1/3) + 4*sqrt(2/((2/3)^(2/3)*(9+sqrt(177))^(1/3) - 4*(2/(27+3*sqrt(177)))^(1/3)))) = 1.59792093355003207476470...

cp's OEIS Frontend

A225227 The n X n X n dots problem: minimal number of straight lines (connected at their endpoints) required to pass through n^3 dots arranged in an n X n X n grid, without exiting from the box [0, n] X [0, n] X [0, n].

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A373537 Decimal expansion of the Euclidean length of the shortest minimum-link polygonal chains joining all the vertices of the cube [0,1]^3.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A374149 Decimal expansion of the minimum volume of an axis-aligned bounding box which includes the shortest minimum-link polygonal chain joining all the vertices of the cube {0,1}^3.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A374883 Decimal expansion of phi*(2*phi + 1) (i.e., (7 + 3*sqrt(5))/2), where phi is the golden ratio.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

A374260 Decimal expansion of the Euclidean length of the shortest circuit covering all the vertices of the cube [0,1]^3.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A374883 Decimal expansion of phi(2phi + 1) (i.e., (7 + 3*sqrt(5))/2), where phi is the golden ratio.