Detailed mathematical approach

Problem Summary

Start with the single-node tree \(T_1\). For each \(m\ge 2\), form \(T_m\) by making \(m\) the new root and reattaching the chain obtained from \(T_{m-1}\) by starting at the old root and repeatedly following the greatest child. Let \(S(n,k)\) be the sum of the labels on the unique path from node \(k\) to the root \(n\) in \(T_n\).

The implementation must evaluate this path sum for the very large input \((n,k)=\left(10^{17},9^{17}\right)\). The crucial observation is that the recursive tree rule has a direct binary description, so the tree never has to be built explicitly.

Mathematical Approach

The recursive definition looks structural, but the actual parent relation turns out to depend only on powers of two. Once that relation is identified, the path from \(k\) to \(n\) becomes a simple process of clearing the leading bit of the remaining gap.

Step 1: Identify the chain moved at each insertion

An induction on the recursive construction shows that, just before node \(m+1\) is inserted, the chain lifted from the old root is

$m,\ m-1,\ m-3,\ m-7,\ \dots,\ m+1-2^j,$

for every power \(2^j\le m\).

Equivalently, when a new root \(x\) is created, its direct children are exactly

$x-1,\ x-2,\ x-4,\ x-8,\dots.$

So the recursive tree is secretly organized by offsets that are powers of two.

Step 2: Derive the final parent of any node

A node \(y\) is attached to a later node \(x\) exactly when \(x-y\) is a power of two. Since later insertions may reattach \(y\) again, its parent in the final tree \(T_n\) is the largest such \(x\) with \(x\le n\).

Therefore, for every \(y<n\),

$\operatorname{parent}_n(y)=y+2^{\lfloor \log_2(n-y)\rfloor}.$

This is the key greedy rule: from the current node, move upward by the largest power of two that still fits in the remaining distance to \(n\).

Step 3: Rewrite the climb through the remaining gap

Let \(x_0=k\), and define the remaining gap by

$r_t=n-x_t.$

Applying the parent formula gives

$x_{t+1}=x_t+2^{\lfloor \log_2 r_t\rfloor}, \qquad r_{t+1}=r_t-2^{\lfloor \log_2 r_t\rfloor}.$

Thus each step removes the most significant set bit of the current gap. When the gap becomes \(0\), the climb has reached \(n\).

Step 4: Express the whole path from the binary expansion of \(n-k\)

Write the difference as

$n-k=\sum_{i=1}^{s}2^{e_i}, \qquad e_1>e_2>\cdots>e_s\ge 0.$

Because the algorithm removes one leading bit at a time, the visited nodes are exactly

$x_j=k+\sum_{i=1}^{j}2^{e_i}\qquad (0\le j\le s),$

where the empty sum for \(j=0\) is \(0\).

Therefore the path sum is

$S(n,k)=\sum_{j=0}^{s}x_j=(s+1)k+\sum_{i=1}^{s}(s-i+1)2^{e_i}.$

So the tree problem is equivalent to a weighted sum of the set bits of \(n-k\).

Step 5: Worked example

Take \((n,k)=(10,3)\). Then

$n-k=7=2^2+2^1+2^0.$

The remaining gaps are

$7\to 3\to 1\to 0,$

so the visited nodes are

$3\to 7\to 9\to 10.$

Hence

$S(10,3)=3+7+9+10=29.$

This matches the small checkpoint used by the implementation and shows concretely that each move clears one binary digit of the difference.

How the Code Works

The C++, Python, and Java implementations all use the same fast loop. They keep the current node and the running sum, compute the largest power of two not exceeding the remaining gap \(n-\text{current}\), jump upward by that amount, and add the new node to the sum.

No explicit tree nodes, adjacency lists, or recursive traversal are needed for the real input. One implementation also includes tiny cross-checks on small values, confirming that the binary parent rule agrees with the recursive construction.

Complexity Analysis

Let \(s\) be the number of \(1\)-bits in the binary expansion of \(n-k\). Each iteration removes exactly one of those bits, so the running time is \(O(s)\) and the memory usage is \(O(1)\). Since \(s\le \lfloor \log_2(n-k)\rfloor+1\), the method is also \(O(\log n)\) in the worst case.

Footnotes and References

1. Project Euler problem page: https://projecteuler.net/problem=872
2. Powers of two: Wikipedia — Power of two
3. Binary numbers: Wikipedia — Binary number
4. Hamming weight: Wikipedia — Hamming weight
5. Tree theory basics: Wikipedia — Tree (graph theory)