प्रोजेक्ट यूलर समस्या # 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. तो प्रश्न सबसे कम एन खोजने के लिए है ताकि पी (एन) के कारकों में छः 2 और छः 5 हो।

Answer 3

क्या आपने अभी तक 31 या 76 समस्याएं हैं? वे एक अच्छा सेट बनाते हैं जो हर बार एक ही आधार समस्या का सामान्यीकरण है। आसान प्रश्नों से आपको 78 के लिए समाधान में अंतर्दृष्टि मिल सकती है।

Answer 4

यह समस्या वास्तव में पूर्णांक विभाजन के अनुक्रम में पहला शब्द ढूंढने के लिए कह रही है जो 1,000,000 से विभाजित है।

एक पूर्णांक का एक विभाजन, एन, सकारात्मक पूर्णांक के योग के कितने तरीकों का वर्णन करने का एक तरीका है, ≤ n, आदेश के बावजूद बराबर एन के साथ जोड़ा जा सकता है। फंक्शन पी (एन) एन के लिए विभाजन की संख्या को इंगित करने के लिए प्रयोग किया जाता है। नीचे हम अपने 5 "सिक्कों" को 7 विभाजनों का मूल्यांकन करने के लिए जोड़ते हैं, जो पी (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 तथाकथित सामान्यीकृत पेंटगोनल संख्याओं की आवश्यकता होती है, जो एन (3 एन -1)/2 के साथ 0, ± 1, ± 2, ± 3 ... के साथ दी जाती है, जिनमें से कुछ 0, 1, 2, 5, 7, 12, 15, 22, 26, 35, ... (स्लोएन ए001318)।

हम निम्नलिखित पैदा समारोह जो घातांक के रूप में हमारे पंचकोणीय संख्या का उपयोग करता है:

1 - क्ष - क्ष^2 + क्ष^5 + क्ष^7 - क्ष^12 - क्ष^15 + क्ष^22 + क्यू^26 + ...

blog.dreamshire.com पर मेरे ब्लॉग में एक पर्ल प्रोग्राम है जो इसे 10 सेकंड से कम में हल करता है।