Советы по проекту Эйлера Проблема № 78

Это проблема: Проблема № 78

Это сводит меня с ума. Я работаю над этим в течение нескольких часов, и мне удалось уменьшить сложность поиска количества способов складывать монеты n в O(n/2), но даже с этими улучшениями и начиная с n, для которого p(n) близок к одному миллиону, я до сих пор не могу получить ответ менее чем за минуту. Совсем нет.

Есть ли подсказки, которые могли бы помочь мне в этом?

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

Ответ 1

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

Лучше всего использовать рекурсию на основе пятиугольной теоремы чисел в следующем разделе. Доказательство этой теоремы не прямолинейно, поэтому я не думаю, что авторы проблемы ожидают, что вы придумаете теорему самостоятельно. Скорее, это одна из проблем, когда они ожидают поиска литературы.

Ответ 2

Эта проблема действительно просит найти первый член в последовательности целых разделов, которые делятся на 1 000 000.

Разделение целого числа, n, является одним из способов описания того, сколько способов сумма положительных чисел ≤ n может быть сведена вместе к равному n независимо от порядка. Функция p (n) используется для обозначения числа разделов для n. Ниже мы показываем наши 5 "монеты" как слагаемые для оценки 7 разделов, то есть p (5) = 7.

5 = 5 = 4 + 1 = 3 + 2 = 3 + 1 + 1 = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 + 1 + 1 + 1

Мы используем функцию генерации, чтобы создать серию, пока не найдем требуемое n. Генерирующая функция требует не более 500 так называемых обобщенных пятиугольных чисел, определяемых n (3n-1)/2 с 0, ± 1, ± 2, ± 3..., первые из которых равны 0, 1, 2, 5, 7, 12, 15, 22, 26, 35,... (Sloanes A001318).

Мы имеем следующую производящую функцию, которая использует наши пятиугольные числа как показатели:

1 - q - q ^ 2 + q ^ 5 + q ^ 7 - q ^ 12 - q ^ 15 + q ^ 22 + q ^ 26 +...

В моем блоге на blog.dreamshire.com есть программа perl, которая решает это менее чем за 10 секунд.

Ответ 3

У вас были проблемы 31 или 76? Они образуют хороший набор, который является обобщением одной и той же базовой проблемы каждый раз. Выполнение более простых вопросов может дать вам представление о решении для 78.

Ответ 4

Вот несколько советов:

Делимость на миллион - это не то же самое, что просто больше миллиона. 1 миллион = 1 000 000 = 10 ^ 6 = 2 ^ 6 * 5 ^ 6.
Итак, вопрос заключается в том, чтобы найти наименьшее n, так что факторы p (n) содержат шесть 2 и шесть 5.