%I
%S 1,1,4,14,41
%N 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.
%C This is an ndimensional generalization of the wellknown "Nine Dots Problem".
%C Bounds for this problem, for n >= 5, are:
%C ceiling((3^n + n  3)/2) <= a(n) <= 42*3^(n  4)  1.
%C a(5) is 123, 124 or 125, since 123 is the lower bound calculated as above and 125 is the best solution found as of Aug 06 2018.
%C Except for n < 2, the a(n) represent "outside the box" solutions.
%H M. Ripà, <a href="http://www.scribd.com/doc/138937268/Extended9DotsPuzzletonxnxxnDotsGeneralSolvingMethod">nxnx...xn Dots Puzzle</a>
%H M. Ripà, <a href="http://nntdm.net/volume202014/number1/5971/">The rectangular spiral or the n1 X n2 X ... X nk Points Problem</a>, Notes on Number Theory and Discrete Mathematics, 2014, 20(1), 5971.
%H M. Ripà, <a href="http://nntdm.net/volume252019/number2/6875/">The 3 X 3 X ... X 3 Points Problem solution</a>, Notes on Number Theory and Discrete Mathematics, 2019, 25(2), 6875.
%H Marco Ripà, <a href="/A261547/a261547_1.pdf">The n X n X n Points Problem Optimal Solution</a>
%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Thinking_outside_the_box#Nine_dots_puzzle">Nine dots puzzle</a>
%F a(n) = ceiling((3^n + n  3)/2), for any n >= 2 (conjectured).
%e For n=4, a(4) = 41. You cannot touch (the centers of) the 3^4 = 81 dots using fewer than 41 straight lines, following the "Nine Dots Puzzle" basic rules.
%Y Cf. A058992, A225227.
%K nonn,more,hard
%O 0,3
%A _Marco Ripà_, Aug 24 2015
%E a(4) added by _Marco Ripà_, Aug 06 2018
