Советы для проекта Эйлера Задача № 78

Question

Это проблема в вопросе: Problem #78

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

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

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

Answer 1

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

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

Answer 2

здесь некоторые намеки:

1. Делимость на один миллион, не то же самое, только будучи больше, чем один миллион. 1 миллион = 1 000 000 = 10^6 = 2^6 * 5^6.

2. Итак, вопрос заключается в том, чтобы найти наименьшее значение n, чтобы факторы p (n) содержали шесть 2 и шесть 5.

Answer 3

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

Answer 4

Эта проблема действительно просит найти первый член в последовательности целых разделов, которые делятся на 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, ... (Sloane's A001318).

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

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

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