Задача 829
Целочисленное слияние
Для любого целого числа $n>1$ можно определить двоичное дерево множителей $T(n)$ следующим образом:
- Дерево с единственным узлом $n$, если $n$ - простое число.
- Двоичное дерево с корневым узлом $n$, левым поддеревом $T(a)$ и правым поддеревом $T(b)$, если $n$ - не простое число. Здесь $a$ и $b$ - положительные целые числа, такие что $n = ab$, $a\le b$ и $b-a$ имеет наименьшее возможное значение.
Например, $T(20)$:
Определим $M(n)$ как наименьшее число, чье дерево множителей идентично по форме дереву множителей числа $n!!$, двойного факториала от $n$.
Например, рассмотрим $9!! = 9\times 7\times 5\times 3\times 1 = 945$. Нижк показано дерево множителей для $945$ вместе с деревом множителей для $72$, которое является наименьшим числом, с деревом множителей такой же формы. Посему $M(9) = 72$.
Найдите $\displaystyle\sum_{n=2}^{31} M(n)$.
© Проект Эйлера | Translated problems from ProjectEuler.net