這是有問題的問題：Problem #78項目歐拉提示問題＃78
這讓我瘋狂。我已經在此工作了幾個小時，並且我已經能夠減少找到將n硬幣堆疊到O(n/2)的方法的數量的複雜性，但是即使具有那些改進和從n開始，其中p(n)已接近一百萬，我仍然無法在一分鐘內得出答案。實際上並非如此。
有沒有什麼提示可以幫助我呢？
請記住，我不想要一個完整的解決方案，不應該有任何功能解決方案張貼在這裏，以免破壞其他人的問題。這就是爲什麼我沒有包含任何代碼。
Wikipedia可以幫助你在這裏。我假設你已經擁有的解決方案是遞歸，例如「中間函數」一節中的那個。這可以用來找到歐拉問題的解決方案，但並不快。
更好的方法是在下一節中使用基於pentagonal number theorem的遞歸。這個定理的證明不是直截了當的，所以我不認爲問題的作者希望你自己提出這個定理。相反，這是他們期望進行一些文獻檢索的問題之一。
這裏一些提示：
整除一百萬是不是擺明大於一百萬同樣的事情。 100萬= 1,000,000 = 10^6 = 2^6 * 5^6。
所以問題是要找到一個最低的n，以便p（n）的因子包含六個2和六個5。
你確定（2.）嗎？如果（2）爲真，這將是一個合理的（甚至是最好的）方法，但AFAIK沒有p（n）的乘法標識：http://en.wikipedia.org/wiki/Partition_%28number_theory%29 – ShreevatsaR 2009-11-19 19:04:10
此問題實際上是要求查找可由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，...（斯隆的A001318）。
我們有一個使用我們的五角數作爲指數如下生成函數：
1 - q - C 1-4 2 + Q^5 + Q^7 - C 1-4 12 - C 1-4 15 + Q^22 + C 1-4 26 + ...
我在blog.dreamshire.com博客有下10秒解決了這個在Perl程序。
您試圖在不到一分鐘內解決的任何特定原因？ – 2009-11-19 18:20:41
這就是歐拉項目的經驗法則。直言不諱：如果算法在一分鐘內無法解決，它會很糟糕，因此不是一個好的解決方案。我想要一個好的解決方案。 – 2009-11-19 18:44:19
我不能給你任何具體的建議，但我前一段時間發佈了一些一般性建議：http://stackoverflow.com/questions/1537306/recommended-reading-for-solving-project-euler-problems/1537531#1537531 – starblue 2009-11-19 18:49:17