Задача 829
Целочисленное слияние

Для любого целого числа $n>1$ можно определить двоичное дерево множителей $T(n)$ следующим образом:

  • Дерево с единственным узлом $n$, если $n$ - простое число.
  • Двоичное дерево с корневым узлом $n$, левым поддеревом $T(a)$ и правым поддеревом $T(b)$, если $n$ - не простое число. Здесь $a$ и $b$ - положительные целые числа, такие что $n = ab$, $a\le b$ и $b-a$ имеет наименьшее возможное значение.

Например, $T(20)$:

p829_example1.jpg

Определим $M(n)$ как наименьшее число, чье дерево множителей идентично по форме дереву множителей числа $n!!$, двойного факториала от $n$.

Например, рассмотрим $9!! = 9\times 7\times 5\times 3\times 1 = 945$. Нижк показано дерево множителей для $945$ вместе с деревом множителей для $72$, которое является наименьшим числом, с деревом множителей такой же формы. Посему $M(9) = 72$.

p829_example2.jpg

Найдите $\displaystyle\sum_{n=2}^{31} M(n)$.

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net