A242461 Decimal expansion of the first positive solution to exp(1-1/x)/x = 1/2, a binary search tree constant.

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

Offset

0,1

Comments

The saturation level S_n of a binary search tree defined by a random n-permutation is such that S_n/log(n) converges to 0.3733646... in probability.

References

Steven R. Finch, Mathematical Constants, Cambridge University Press, 2003, pp. 349-352.

Links

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

Luc Devroye, A Note on the Height of Binary Search Trees. McGill University, Montreal, Canada (1986).

Formula

-1/W(-1, -1/(2*e)) where W is the Lambert W function (ProductLog).

Example

0.373364617701674084248448436679270595...

Mathematica

RealDigits[-1/ProductLog[-1, -1/(2*E)], 10, 100] // First

Crossrefs

Cf. A076615, A076616, A195581, A195582, A195596.

Sequence in context: A283245 A066065 A145511 * A065443 A198350 A117190

Adjacent sequences: A242458 A242459 A242460 * A242462 A242463 A242464

Keyword

nonn,cons

Author

Jean-François Alcover, May 15 2014

Status

approved