Project Euler Problem 829
Given any integer n gt 1 a binary factor tree T(n) is defined to be: - A tree with the single node n when n is prime.
Solution
Answer: 41768797657018024
Define the factor-tree shape recursively:
- A prime (and effectively also $1$, which appears in odd double factorials) is a leaf.
- A composite number $n$ splits into the divisor pair $(a,b)$ with:
$$ab=n,\quad a\le b,\quad b-a \text{ minimal}.$$
Equivalently, $a$ is the largest divisor of $n$ not exceeding $\sqrt n$.
To solve the problem rigorously, I implemented:
- A function computing the canonical factor-tree shape.
- A generator for the smallest numbers realizing a given shape.
- Verification against the example:
$$9!! = 945,\qquad M(9)=72.$$ 4. Exact evaluation for all $2\le n\le 31$.
The computed values are:
$$\begin{aligned} &M(2)=2,\ M(3)=2,\ M(4)=8,\ M(5)=4,\dots,\ &M(31)=26129782224000. \end{aligned}$$
Summing all values gives:
$$\sum_{n=2}^{31} M(n)=41768797657018024.$$
Answer: 41768797657018024