A374148 Integer part of (2^(n - 1) - 1)*sqrt(3) + 1.

0, 1, 2, 6, 13, 26, 54, 110, 220, 442, 886, 1772, 3546, 7093, 14188, 28377, 56755, 113510, 227022, 454045, 908092, 1816186, 3632373, 7264746, 14529494, 29058989, 58117980, 116235961, 232471923, 464943847, 929887695, 1859775392, 3719550786, 7439101572

Offset: 0

Author

Marco Ripà, Jun 28 2024

Keywords

• nonn
• easy

Comments

It is reasonable to assume that this sequence describes the Euclidean length of the shortest tree joining the 2^n vertices of the hypercube {0,1}^n since David E. Speyer and Peter Taylor have constructively provided the upper bound sqrt(3)*(2^(n - 1) - 1) + 1, for any n >= 2, on the total Euclidean length of any tree joining all the 2^n vertices of the unit cube. Furthermore, professor Speyer has proved that the optimal solution must be a Steiner tree whose interior vertices are all trivalent and whose angles are mandatorily equal to Pi/3 radians.

References

• F. K. Hwang, D. S. Richards, and P. Winter, The Steiner tree problem, Annals of Discrete Mathematics, Amsterdam: North-Holland, 53 (1992).

Links

• Robert Bridges, Minimal Steiner Trees for Three Dimensional Networks, Mathematical Gazette, Vol. 78, July 1994, Number 482, pp. 157-162.
• Fan Chung, Martin Gardner, and Ron Graham, Steiner trees on a checkboard, Mathematics Magazine, Vol. 62, April 1989, pp. 83-96.
• MathOverflow, Joining the 2^k points of {0,1}^k with the shortest tree.

Crossrefs

Cf. A002194.

Programs

Mathematica

a[n_]:= Floor[Sqrt[3]*(2^(n - 1) - 1) + 1]; Array[a,34,0] (* Stefano Spezia, Jun 29 2024 *)

Python

from math import isqrt
def A374148(n): return 1+isqrt(3*((1<Chai Wah Wu, Jun 30 2024

Formula

a(n) = floor(sqrt(3)*(2^(n - 1) - 1) + 1).