Решил вчера очередную задачку по программированию с projecteuler.net

Задача такая. Некое число монет можно разложить по стопкам разными способами. 1 монета - 1 способ, 2 монеты - 2 способа, 3 монеты - 3 способа, и т.д.:

1 ( 1) : 1
2 ( 2) : 2; 1+1
3 ( 3) : 3; 2+1; 1+1+1
4 ( 5) : 4; 3+1; 2+2; 2+1+1; 1+1+1+1
5 ( 7) : 5; 4+1; 3+2; 3+1+1; 2+2+1; 2+1+1+1; 1+1+1+1+1
6 (11) : 6; 5+1; 4+2; 4+1+1; ...

Требуется найти такое минимальное число монет, для которого число разложений нацело делится на миллион.

Я эти задачки делаю так. Сначала пытаюсь прийти хоть к какому-то решению, которое бы работало. По возможности, конечно, чтобы было более-менее оптимально, но тут уж как получится. Иногда удается решить только брутфорсом.

Если оно решается за некое приличное время, оставляю, как есть. Если же время неприличное, то уже лезу либо на местный форум (который становится доступным только для тех, кто задачку решил) или в гугл, чтобы найти, какая математика может стоять за моей проблемой.

Для этой задачи я написал брутфорс, который правильно работал на небольших числах, но очень быстро стопорился с ростом входного числа.
Потом я этот брутфорс оптимизировал несколько раз.
Потом я очень долго сидел, обложившись бумагами, и в итоге смог вывести некую формулу, которая ускорила мой алгоритм в несколько (может даже десятков) раз.
Этот алгоритм я еще несколько раз переписывал, и в итоге получил рабочее решение, при помощи которого я бы уже мог найти ответ.

Но не смог.

Проблема была в том, что мое решение требовало много памяти. И чем дальше, тем больше.
Последние пару месяцев прога работала на 5 потоках, практически нонстоп, покрывая в день порядка 500-1000 чисел.
Ну то есть понятно, что это дохлый номер, и надо искать более оптимальное решение, но тут я уже пошел на принцип.

Вчера я дошел до момента, когда 32 гигов памяти мне тупо не хватило.

На этом месте я понял, что пора остановиться. С начала работы над задачей прошло 4,5 месяца.
Полез в гугл, за пару минут нагуглил Partition Numbers.
За пол часа написал алгоритм.
За пару часов его отладил.
За 80 секунд получил решение. Число из 257 знаков.

Математика - великая штука.