A261547 The 3 X 3 X ... X 3 dots problem (3, n times): minimal number of straight lines (connected at their endpoints) required to pass through 3^n dots arranged in a 3 X 3 X ... X 3 grid.

1, 1, 4, 13, 40, 121, 364, 1093, 3280, 9841, 29524, 88573, 265720, 797161, 2391484, 7174453, 21523360, 64570081, 193710244, 581130733, 1743392200, 5230176601, 15690529804, 47071589413, 141214768240, 423644304721, 1270932914164

Offset: 0

Author

Marco Ripà, Aug 24 2015

Keywords

• nonn

Comments

Except for the first term a duplicate of A003462.

This is an n-dimensional generalization of the well-known "Nine Dots Problem".

Except for n < 2, the a(n) represent "outside the box" solutions, but (for any n) the minimal covering trail C(n) is still inside a box of (hyper)volume 3^n units^n. - Marco Ripà, Jul 19 2020

Examples

			For n=5, a(5) = 121. You cannot touch (the centers of) the 3^5 = 243 points using fewer than 121 straight lines, following the "Nine Dots Puzzle" basic rules.
		

Links

• 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à, 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.
• Wikipedia, Nine dots puzzle

Crossrefs

Cf. A003462, A058992, A225227.

Programs

Mathematica

Join[{1}, (3^Range[30]-1)/2] (* Paolo Xausa, Jan 31 2024 *)

Formula

a(n) = (3^n - 1)/2 = A003462(n), for n >= 1. - Marco Ripà, Jul 19 2020

Extensions

a(4) added by Marco Ripà, Aug 06 2018

a(3)-a(4) corrected and more terms added by Marco Ripà, Jul 19 2020