Задача 159
Суммы цифровых корней множителей

Сложное число может быть разложено на множители разными путями. К примеру, если исключить умножение на единицу, 24 может быть разложено семью разными способами:

24 = 2x2x2x3
24 = 2x3x4
24 = 2x2x6
24 = 4x6
24 = 3x8
24 = 2x12
24 = 24

Напомним, что цифровой корень числа по основанию 10 можно найти, складывая цифры этого числа, и повторяя этот процесс, пока в результате не получится число меньше 10. Таким образом, цифровой корень числа 467 равен 8.

Назовем Суммой Цифровых Корней (СЦК) сумму цифровых корней каждого из множителей числа.
Таблица ниже демонстрирует все значения СЦК для числа 24.

Разложение на множителиСумма Цифровых Корней
2x2x2x3
9
2x3x4
9
2x2x6
10
4x6
10
3x8
11
2x12
5
24
6

Максимальная СЦК для 24 равна 11.
Функция mdrs(n) возвращает максимальную СЦК для числа n. Таким образом, mdrs(24)=11.
Найдите mdrs(n) для 1 < n < 1 000 000.

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