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,3

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

Table of n, a(n) for n=0..33.

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.

Formula

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

Mathematica

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

Prog

(Python)
from math import isqrt
def A374148(n): return 1+isqrt(3*((1<<n-1)-1)**2) if n else 0 # Chai Wah Wu, Jun 30 2024

Crossrefs

Cf. A002194.

Sequence in context: A192953 A353232 A275970 * A124677 A034465 A182614

Adjacent sequences: A374145 A374146 A374147 * A374149 A374150 A374151

Keyword

nonn,easy

Author

Marco Ripà, Jun 28 2024

Status

approved