Задача 88
Числа произведения-суммы

Каждое натуральное число N, которое можно записать как в виде суммы, так и в виде произведения элементов множества, состоящего из по крайней мере двух натуральных чисел {a_(1), a_(2), ... , a_(k)}, называется числом произведения-суммы: N = a_(1) + a_(2) + ... + a_(k) = a_(1) × a_(2) × ... × a_(k).

К примеру, 6 = 1 + 2 + 3 = 1 × 2 × 3.

Для заданного множества размером k мы будем называть наименьшее число N, обладающее данным свойством, наименьшим числом произведения-суммы. Наименьшими числами произведения-суммы множеств размером k = 2, 3, 4, 5 и 6 являются следующие числа:

k=2: 4 = 2 × 2 = 2 + 2
k=3: 6 = 1 × 2 × 3 = 1 + 2 + 3
k=4: 8 = 1 × 1 × 2 × 4 = 1 + 1 + 2 + 4
k=5: 8 = 1 × 1 × 2 × 2 × 2 = 1 + 1 + 2 + 2 + 2
k=6: 12 = 1 × 1 × 1 × 1 × 2 × 6 = 1 + 1 + 1 + 1 + 2 + 6

Отсюда следует, что сумма всех минимальных чисел произведения-суммы при 2≤k<6 равна 4+6+8+12 = 30. Обратите внимание на то, что число 8 учитывалось в сумме лишь один раз.

Т.к. множеством минимальных чисел произведения-суммы при 2≤k<12 является {4, 6, 8, 12, 15, 16}, то их сумма равна 61.

Какова сумма всех минимальных чисел произведения-суммы при 2≤k<12000?

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