Neue Übersetzung für Problem 872

Hinweise zur Erstellung von Übersetzungen

Als Basis für jede Übersetzung dient der Text von projecteuler.net.
Der Originaltitel und Text im untenstehenden Formular sind zu übersetzen.
Der HTML-Quelltext in seiner Struktur sollte im Allgemeinen unverändert bleiben.
Querverweise zu anderen Problemen sollten in der Form /problem=?? erfolgen.
Wenn Grafiken oder Dateien verwendet werden, sollte die URL https://projecteuler.net/... verwendet werden.
Die Sie-Form benutzen.

Titel

Inhalt

A sequence of rooted trees $T_n$ is constructed such that $T_n$ has $n$ nodes numbered $1$ to $n$.

The sequence starts at $T_1$, a tree with a single node as a root with the number $1$.

For $n &gt; 1$, $T_n$ is constructed from $T_{n-1}$ using the following procedure:
<ol>
<li>Trace a path from the root of $T_{n-1}$ to a leaf by following the largest-numbered child at each node.</li>
<li>Remove all edges along the traced path, disconnecting all nodes along it from their parents.</li>
<li>Connect all orphaned nodes directly to a new node numbered $n$, which becomes the root of $T_n$.</li>
</ol>

For example, the following figure shows $T_6$ and $T_7$. The path traced through $T_6$ during the construction of $T_7$ is coloured red.
<div class="center">
<img src="resources/images/0872_tree.png?1703839264" alt="0872_tree.png"></div>

Let $f(n, k)$ be the sum of the node numbers along the path connecting the root of $T_n$ to the node $k$, including the root and the node $k$. For example, $f(6, 1) = 6 + 5 + 1 = 12$ and $f(10, 3) = 29$.

Find $f(10^{17}, 9^{17})$.

​x
 
<p>A sequence of rooted trees $T_n$ is constructed such that $T_n$ has $n$ nodes numbered $1$ to $n$.</p>​<p>The sequence starts at $T_1$, a tree with a single node as a root with the number $1$.</p>​<p>For $n &gt; 1$, $T_n$ is constructed from $T_{n-1}$ using the following procedure:</p><ol><li>Trace a path from the root of $T_{n-1}$ to a leaf by following the largest-numbered child at each node.</li><li>Remove all edges along the traced path, disconnecting all nodes along it from their parents.</li><li>Connect all orphaned nodes directly to a new node numbered $n$, which becomes the root of $T_n$.</li></ol>​​<p>For example, the following figure shows $T_6$ and $T_7$. The path traced through $T_6$ during the construction of $T_7$ is coloured red.</p><div class="center"><img src="resources/images/0872_tree.png?1703839264" alt="0872_tree.png"></div>​​<p>Let $f(n, k)$ be the sum of the node numbers along the path connecting the root of $T_n$ to the node $k$, including the root and the node $k$. For example, $f(6, 1) = 6 + 5 + 1 = 12$ and $f(10, 3) = 29$.</p>​<p>Find $f(10^{17}, 9^{17})$.</p>

Sie erklären sich einverstanden, dass die Übersetzung unter der Creative Commons Lizenz CC BY-NC-SA 4.0 veröffentlicht wird. Wenn Sie wollen, dass die Übersetzung Ihnen zugeordnet werden kann, müssen Sie sich einloggen (oben rechts), andernfalls ist sie anonym.