एक अंश पहेली
यह कंप्यूटर-पहेली टैग और नो-कंप्यूटर टैग दोनों के साथ एक पहेली है ।
हमारे पास पांच अंशों की सूची है:
$$11/5, 30/77, 1/11, 21/2, 5/7.$$
एक पूर्णांक के साथ शुरू $x$, हम निम्नलिखित ऑपरेशन करते हैं: प्रत्येक चरण पर, गुणा करें $x$ उपरोक्त सूची में पहला अंश (बाएं से दाएं) जो पूर्णांक परिणाम देता है।
यदि सूची में ऐसा कोई अंश नहीं है, तो प्रक्रिया समाप्त हो जाती है और इसका मूल्य $x$ अंतिम परिणाम है।
उदाहरण: से शुरू $x = 2$
पहला कदम: इसके द्वारा गुणा करें $21/2$, जो देता है $21$।
दूसरा चरण: इसके द्वारा गुणा करें $5/7$, जो देता है $15$।
तीसरा चरण: इसके द्वारा गुणा करें $11/5$, जो देता है $33$।
चौथा चरण: इसे गुणा करें $1/11$, जो देता है $3$।
हम देखते है कि $x = 3$ गुणा के रूप में अंतिम परिणाम है $3$ पांच अंशों में से कोई भी गैर-पूर्णांक परिणाम देगा।
प्रश्न: अगर हम शुरुआत करते हैं $x = 2^{1234567}$, तो अंतिम परिणाम के अंतिम तीन अंक क्या होंगे?
टिप्पणी:
यह कुछ हद तक अच्छी तरह से जाना जाता है, और मैं जानबूझकर नाम का उल्लेख नहीं करता हूं, क्योंकि यह इतना सरल होना चाहिए कि इसे हल करने के लिए कोई अतिरिक्त ज्ञान की आवश्यकता न हो।
बेशक, आप अपने जवाब में नाम इंगित करने के लिए स्वागत कर रहे हैं!
जवाब
हम उसका निरीक्षण करते हैं
केवल एक अंश में 2 का हर होता है
जैसा कि हमारे पास x = 2 ^ 1234567 है, हम इसे प्लग इन करने का प्रयास कर सकते हैं। हम चीजों को आसान बनाने के लिए संख्याओं के प्रमुख कारक का उपयोग करेंगे।
हम पहली बार 21/2 से गुणा करते हैं, 2 ^ 1234566 * 3 * 7. हो रहा है क्योंकि 21/2 से पहले सभी अंशों में 2, 3 या 7 के अलावा एक प्रमुख कारक है, हम जानते हैं कि फ़ंक्शन 21/2 से गुणा करना जारी रखेगा जब तक 2 के कोई कारक नहीं बचे हैं। यह हमें 3 ^ 1234567 * 7 ^ 1234567 के साथ छोड़ देता है।
अगला,
हम 5/7 से गुणा करते हैं। क्योंकि सूची में पहले अंश में 5 का एक भाजक है, हम जानते हैं कि कभी भी हम 5/7 से गुणा करते हैं, हम अनिवार्य रूप से 11/7 से गुणा करेंगे। हम गुणा करते हैं और 3 ^ 1234567 * 7 ^ 1234566 * 11. 30/77 प्राप्त करते हैं। हम 2 * 3 ^ 1234568 * 5 * 7 ^ 1234565 के साथ समाप्त होते हैं। 11/5 से गुणा करने पर हमें 2 * 3 ^ 1234568 * 7 ^ 1234565 * 11 मिलता है।
हमने देखा कि
क्योंकि हमारे पास 7s की इतनी बड़ी राशि है, हम 7s से बाहर चलने तक 30/77 और 11/5 गुणा करेंगे। हम महसूस करते हैं कि हर बार 7 की संख्या 1 से घट जाती है, 2 की संख्या 1 से बढ़ जाती है और 3 की संख्या 1 से बढ़ जाती है। हम 2 और 3 के कारकों की संख्या को 1234565 तक बढ़ाते हैं और 7 के सभी कारकों को निकालते हैं। 2 ^ 1234566 * 3 ^ 2469133 * 11. हम 11 के कारक को हटाने के लिए 1/11 से गुणा करते हैं और 2 ^ 1234566 * 3 ^ 2469133 प्राप्त करते हैं।
यह हमें शुरुआत के अलावा उसी जगह पर छोड़ देता है, सिवाय इसके
हमारे पास 3 के कारकों का एक समूह है और 2 के कारकों की संख्या 1 से कम हो गई है।
क्योंकि हर किसी में 3 का कारक नहीं है,
हम पहले की तरह ही काम करेंगे, बस कई बार। सभी 2s को खत्म करने से हमें 3 ^ 3703699 * 7 ^ 1234566 मिलते हैं। हम 3/7 3703699 * 7 ^ 1234565 * 11. प्राप्त करने के लिए 5/7 और फिर 11/5 से गुणा करते हैं। हम 2 और 3 की शक्तियों को वापस जोड़ते हैं और 7 की सभी शक्तियों को हटाते हैं और 2 की एक शक्ति प्राप्त करते हैं 2 ^ 1234565 * 3 ^ 4938264।
हमने देखा कि
पहली बार 3 की शक्ति (1234567 + 1234566) बढ़ी और इस बार 3 की शक्ति (1234566 + 1234565) बढ़ी। इसका मतलब है कि 2 की शक्ति के लिए, यह 3 बाय (2x-1) की शक्ति में वृद्धि करेगा। इसका मतलब 3 की शक्ति होगी$\sum_{i=1}^{1234567} 2i-1$ हम प्राप्त करने के लिए योग के गुणों का उपयोग कर सकते हैं $2*\sum_{i=1}^{1234567} i - 1234567$। हम जानते हैं कि पहले का योग$n$ सकारात्मक पूर्णांक है $\frac{n*(n+1)}{2}$, तोह फिर $\sum_{i=1}^{1234567} i = 1234567*1234568/2 = 762078456028$, तोह फिर $2*\sum_{i=1}^{1234567} i - 1234567 = 1524155677489$
हम देखते है कि
अंतिम उत्तर 3 ^ 1524155677489 है, और क्योंकि 3 ^ x के अंतिम 3 अंक हर 100 बार दोहराते हैं, हमें केवल 3 (मॉड 100) की शक्ति लेने की आवश्यकता है, जो कि 89 है।
इसका मतलब है कि हमें केवल अंतिम 3 अंक खोजने की आवश्यकता है
3 ^ 89।
हम जानते हैं कि अंतिम 3 अंक
3 ^ 10 049 हैं,
जिसका अर्थ है अंतिम 3 अंक
3 ^ 20 केवल 49 ^ 2 या 401 के अंतिम 3 अंक हैं,
जिसका अर्थ है अंतिम 3 अंक
3 ^ 40 401 ^ 2, या 801 के अंतिम 3 अंक हैं
जिसका अर्थ है अंतिम 3 अंक
3 ^ 80 सिर्फ 801 ^ 2, या 601 के अंतिम 3 अंक हैं
जिसका अर्थ है अंतिम 3 अंक
3 ^ 89 केवल 601 * के अंतिम 3 अंक (3 ^ 9 के अंतिम 3 अंक) हैं।
हम जानते हैं कि अंतिम 3 अंक
3 ^ 9 केवल 683 हैं, जिसका अर्थ है कि 3 ^ 89 के अंतिम 3 अंक 601 * 683 के अंतिम 3 अंक हैं, जो 483 हैं।
इसका मतलब हमारा अंतिम उत्तर है
483।
डिस्क्लेमर: मेरी गणना थोड़ी गड़बड़ है, और एक एकल गलत अनुमान पूरे उत्तर को गलत बना देगा, लेकिन सामान्य समाधान अभी भी सही होना चाहिए।
मैं स्नोबिश के रूप में नहीं आना चाहता लेकिन आर्थिक रूप से कुछ साबित करने / गणना करने में मूल्य है। तो चलिए दूसरी छमाही (सबूत के एक पागल उच्च पूर्णांक शक्ति के अंतिम तीन अंकों की गणना) ठीक से करते हैं। सबसे पहले, हम प्राप्त करते हैं$3^{100}\equiv 1 \mod 1000$ (यूलर का उपयोग किए बिना $\phi$):
से शुरू $3^5 = 243$ चलो पांचवीं शक्ति को दो बार और लेते हैं: चूंकि हमें केवल अंतिम तीन अंकों की आवश्यकता है, यह द्विपद प्रमेय का उपयोग करके काफी सरल है क्योंकि यह आसानी से देखा जाता है कि तीसरे और सभी निम्नलिखित शब्द 1000 से विभाज्य हैं और इसलिए इसे अनदेखा किया जा सकता है। $3^{25} \equiv (240+3)^5 \equiv 243 + 5\times 81\times 240 + 10\times 27\times 240^2 + ... \equiv 443 \mod 1000$ $3^{125} \equiv (440+3)^5 \equiv 243 + 5\times 81\times 440 \equiv 443 \mod 1000$
इसलिए दोनों मामलों में समान मूल्य है। जैसा कि 3 और 1000 अपेक्षाकृत प्रमुख हैं हम निष्कर्ष निकालते हैं$3^{100} \equiv 1 \mod 1000$
उस स्थापित के साथ हमें कंप्यूटिंग का एक दर्द रहित तरीका मिल गया
$3^{89}$। जो हमने अभी करके दिखाया है वह हमारे पास है$3^{89}\equiv \frac 1 {3^{11}} \mod 1000$। अब, यह अनुमान लगाना आसान है कि का विलोम$3$ modulo $1000$ है $-333$, की है कि $9$ है $-111$। इस प्रकार:$3^{89}\equiv 3^{-11} \equiv 333\times 111^5 \equiv 333\times \left ( 1 + 5 \times 110 \right ) \equiv 333 \times 551 \equiv 333 + 650 + 500 \equiv 483 \mod 1000$