Expected Depths in Randomly Generated Binary Trees

A full binary tree with n leaves is generated by the following procedure. Initially there is only the root. First, the root is expanded (in this problem, "expanding" a leaf means attaching a left and a right child to that leaf):

[a]

Then, at each subsequent step, one of the current leaves is chosen uniformly at random and expanded. (In the very first step after the initial expansion there are two leaves, so one is chosen with equal probability.) This process repeats until the tree has exactly n leaves. For example, one possible sequence of expansions that yields a tree with 5 leaves is shown below:

[b] and [c]

For a tree produced by this random process (with exactly n leaves), you are to compute the following two expected values:

1. The expected average depth of the leaves.
2. The expected tree depth (i.e. the maximum depth among all leaves). (The root is defined to have depth 0.)

It can be shown that these expectations have the closed‐form expressions below. Let the harmonic number be defined as $$H_m = \sum_{i=1}^{m} \frac{1}{i}.$$ Then, the expected average leaf depth is $$\;\; 2H_n - 2,$$ and the expected tree depth is $$\;\; 2H_{n-1} - 1.$$

Given an integer n (with n ≥ 2), output the two expected values (a floating‐point number each) in one line separated by a space. Print the answers rounded to 6 decimal places.

inputFormat

The input consists of a single integer n (2 ≤ n ≤ 10⁶), representing the number of leaf nodes in the tree.

outputFormat

Output two floating‐point numbers separated by a space: the expected average leaf depth and the expected tree depth. Answers must be rounded to 6 decimal places.

sample

2

1.000000 1.000000