Project Euler Problem 872

Solution

Answer: 2903144925319290239

Let

$$P_n$$

denote the special path traced during the construction of $T_{n+1}$: starting at the root of $T_n$, repeatedly follow the largest-numbered child.

The key to the problem is that these trees have a very rigid binary structure.

1. Mathematical analysis

Step 1: Compute the first few trees

Starting from $T_1$:

• $T_2$: $2 \to 1$
• $T_3$: root $3$ with children $2,1$
• $T_4$: $4\to 3\to1$, and $4\to2$
• $T_5$: $5\to4\to2$, and $5\to3,1$
• $T_6$: $6\to5\to1$, and $6\to4\to2$, $5\to3$

From the statement:

$$f(6,1)=6+5+1=12$$

and

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

Now look at the differences:

• $6-1=5=101_2$
• path: $6,5,1$
• subtractions: $1,4$

and

• $10-3=7=111_2$
• path: $10,9,7,3$
• subtractions: $1,2,4$

This strongly suggests a binary rule.

---

Step 2: The actual structure

Let

$$d=n-k.$$

Write $d$ as a sum of powers of two:

$$d=2^{a_1}+2^{a_2}+\cdots+2^{a_m}, \qquad a_1<a_2<\cdots<a_m.$$

Define cumulative sums

$$s_j=\sum_{i=1}^j 2^{a_i}.$$

Then the path from $n$ to $k$ is

$$n,; n-s_1,; n-s_2,; \ldots,; n-s_m=k.$$

Equivalently:

Starting from $n$, subtract the set bits of $n-k$ from smallest to largest.

---

Why is this true?

We prove it inductively from the construction rule.

Suppose the traced path in $T_n$ is

$$n,;n-b_1,;n-b_1-b_2,\ldots$$

where each $b_i$ is a power of two and strictly increasing.

When constructing $T_{n+1}$, every node on that path becomes a direct child of the new root $n+1$. Hence the new traced path always begins by subtracting the smallest available power of two.

This exactly mirrors the process of removing the lowest set bit repeatedly from $n-k$. Therefore the ancestors of $k$ are obtained by successively adding back the bits of $n-k$ from largest to smallest, or equivalently by subtracting them from smallest to largest.

The examples match perfectly.

---

Step 3: Formula for $f(n,k)$

Let the set bits of $d=n-k$ be

$$b_1<b_2<\cdots<b_m.$$

Define

$$c_j=b_1+\cdots+b_j.$$

Then

$$f(n,k) = \sum_{j=0}^{m} (n-c_j), \qquad c_0=0.$$

So

$$f(n,k) = (m+1)n-\sum_{j=1}^{m} c_j.$$

That is the whole problem.

---

2. Python implementation

def f(n, k):
    """
    Compute the sum of node labels along the path
    from the root of T_n to node k.
    """

    d = n - k

    cumulative = 0
    cumulative_sum = 0
    bit_count = 0

    # Process set bits from smallest to largest
    while d:
        lowest_bit = d & -d

        cumulative += lowest_bit
        cumulative_sum += cumulative
        bit_count += 1

        d -= lowest_bit

    return (bit_count + 1) * n - cumulative_sum

# Small checks from the statement
print(f(6, 1))    # 12
print(f(10, 3))   # 29

# Required value
print(f(10**17, 9**17))

---

3. Code walkthrough

d = n - k

The path structure depends only on the binary expansion of $n-k$.

---

lowest_bit = d & -d

Extracts the smallest set bit of d.

Example:

• if d = 44 = 101100₂
• then lowest_bit = 4.

---

cumulative += lowest_bit

Builds the cumulative sums

$$c_1,c_2,\ldots$$

which correspond exactly to the nodes on the path.

---

cumulative_sum += cumulative

Accumulates

$$c_1+c_2+\cdots+c_m.$$

---

return (bit_count + 1) * n - cumulative_sum

Because the path contains:

$$n,; n-c_1,; n-c_2,\ldots,n-c_m.$$

---

4. Verification on the examples

Example 1

$$n=6,\quad k=1$$

Then

$$d=5=1+4.$$

Cumulative sums:

$$1,\ 5.$$

Path:

$$6,\ 5,\ 1.$$

Therefore

$$f(6,1)=6+5+1=12.$$

Correct.

---

Example 2

$$n=10,\quad k=3$$

Then

$$d=7=1+2+4.$$

Cumulative sums:

$$1,\ 3,\ 7.$$

Path:

$$10,\ 9,\ 7,\ 3.$$

Therefore

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

Correct.

---

5. Compute the required value

For

$$n=10^{17}, \qquad k=9^{17},$$

the algorithm gives

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

The value is reasonable:

• the path length equals the number of set bits of $10^{17}-9^{17}$ plus one,
• here that number is $29+1=30$,
• so the total should be roughly $30\times10^{17}\approx3\times10^{18}$,
• matching the computed magnitude.

---

Answer: 2903144925319290239