दैनिक कोडिंग समस्या: त्रिकोणीय संख्याएँ और बड़े भाजक

एक और समस्या के समाधान के साथ सभी का फिर से स्वागत है! आज, हम त्रिकोणीय संख्याओं और उनके विभाजकों के बारे में बात करेंगे: विशेष रूप से विशाल संख्याओं के बारे में!

जबकि हम प्रकृति में त्रिकोणीय संख्याओं के मेरे शानदार कलात्मक प्रतिनिधित्व की प्रशंसा कर सकते हैं, आइए हमारे सामान्य अस्वीकरण रखें:

1. यह समस्या अद्भुत वेबसाइट द्वारा प्रदान की गई है ProjectEuler.net , जिसे आप सब्सक्राइब कर सकते हैं यहाँ ! हल करने के लिए 800 से अधिक गणित और कोडिंग समस्याएं हैं और उनके बारे में चर्चाओं का एक विशाल संग्रह है। यह सचमुच अपना दिमाग घुमाने और कुछ नया सीखने के लिए एकदम सही उपकरण है! इसे जांचें और अपनी चुनौतियों को भी हल करने का प्रयास करें!

   
   

2. मैं कोई विशेषज्ञ प्रोग्रामर नहीं हूं: बस एक व्यक्ति हूं जिसे इस तरह की चीज़ों के बारे में लिखना अच्छा लगता है और अपने शॉट्स साझा करना पसंद करता है। मुझे यकीन है कि यह इष्टतम समाधान नहीं होगा, इसलिए यदि आपके पास कोई बेहतर समाधान है या इसे अनुकूलित करने के बारे में कोई विचार है तो यदि आप साझा करना चाहते हैं तो आपका हार्दिक स्वागत है!

बहुत हो गई बात, आइए देखें आज की समस्या क्या पेश करती है:

त्रिभुज संख्याओं का क्रम प्राकृतिक संख्याओं को जोड़कर उत्पन्न किया जाता है। तो 7वीं त्रिभुज संख्या 1+2+3+4+5+6+7=28 होगी। पहले दस पद होंगे: 1,3,6,10,15,21,28,36,45,55,…

आइए पहले सात त्रिभुज संख्याओं के गुणनखंडों को सूचीबद्ध करें:

हम देख सकते हैं कि 28 पाँच से अधिक भाजक वाली पहली त्रिभुज संख्या है।

पाँच सौ से अधिक भाजक वाली पहली त्रिभुज संख्या का मान क्या है?

समस्या बिल्कुल सीधी है: हमें यह समझने के लिए कहा गया है कि पहली त्रिकोणीय संख्या क्या है जिसमें 500 से अधिक भाजक हैं। सबसे पहले चीज़ें, आइए बेहतर ढंग से देखें कि त्रिकोणीय संख्या क्या है और विभाजक क्या है।

त्रिकोणीय संख्याएँ

त्रिकोणीय संख्याएँ संख्याओं का एक विशेष उपसमूह होती हैं जो एक निश्चित तक की सभी प्राकृतिक संख्याओं के योग से बनती हैं। उन्हें त्रिकोणीय कहा जाता है क्योंकि आप उन्हें हमेशा त्रिकोण के रूप में व्यवस्थित कर सकते हैं । यहां कुछ उदाहरण दिए गए हैं:

ऊपर की छवि में, यह तीसरी, चौथी और पांचवीं त्रिकोणीय संख्या है। इसलिए, उदाहरण के लिए, तीसरी संख्या 1+2+3 = 6 के रूप में बनती है, चौथी संख्या 1+2+3+4 = 10 के रूप में बनती है, और इसी तरह। आम तौर पर कहें तो, nᵗʰ त्रिकोणीय संख्या, Tₙ, के बराबर है

निस्संदेह, यह गणित की सबसे प्रसिद्ध श्रृंखलाओं में से एक है, जिसे गॉस ने भी प्रस्तुत किया था, जिन्होंने कहा था कि लगातार पूर्णांकों का योग बराबर होता है:

इसलिए मूल रूप से, उदाहरण के लिए, यदि हम तीसरी त्रिकोणीय संख्या की गणना करना चाहते हैं, तो हम बस 3*4/2 = 6 की गणना करते हैं। जब हम अपना समाधान लिखना शुरू करेंगे तो यह बहुत मददगार होगा!

विभाजक

किसी संख्या n के विभाजक (या कारक ) की परिभाषा देना वास्तव में सरल है: यह एक संख्या j है जिसे फिर से n प्राप्त करने के लिए किसी अन्य पूर्णांक k से गुणा किया जा सकता है। उदाहरण के लिए, 3, 18 का भाजक है, क्योंकि हम 3 और 6 को गुणा करके पुनः 18 प्राप्त कर सकते हैं।

हालाँकि, 5, 18 का भाजक नहीं है, क्योंकि ऐसी कोई संख्या k नहीं है जिसे 5 से गुणा करने पर 18 प्राप्त हो।

परिभाषा के अनुसार, हमें एक महत्वपूर्ण गुण भी प्राप्त होता है: यदि j , n का भाजक है क्योंकि n प्राप्त करने के लिए इसे k से गुणा किया जा सकता है , तो k भी n का भाजक है क्योंकि n प्राप्त करने के लिए इसे j से गुणा किया जा सकता है।

इस तरह हम यह सुनिश्चित कर सकते हैं कि संख्या n में हमेशा कम से कम दो भाजक j और k होते हैं (वास्तव में, j हमेशा 1 हो सकता है और k n हो सकता है)।

इसके अलावा, इसे दूसरे तरीके से कहें तो, एक संख्या j, संख्या n का भाजक है यदि n/j का शेषफल 0 के बराबर है। तो, उदाहरण के लिए, 18/3 = 6, और शेषफल 0 है।

हम मॉड्यूलर अंकगणित के साथ इस अवधारणा को बेहतर ढंग से औपचारिक रूप दे सकते हैं कि j , n का भाजक है यदि n % j = 0 है। दूसरे शब्दों में, हम यह दूसरी संपत्ति प्राप्त करते हैं:

तीसरी और आखिरी संपत्ति जिसमें हम रुचि रखते हैं वह यह है कि किसी संख्या n का n/2 से बड़ा कोई भाजक नहीं हो सकता है, बजाय n के। इसे समझना बहुत आसान है. पहली संपत्ति से, हम जानते हैं कि कारक किसी तरह 1,…,n की सीमा में एक साथ "जुड़े" हैं।

ऐसा इसलिए है क्योंकि फिर से, यदि j\n, तो इसका कारण यह है कि j * k = n. इसलिए, k\n भी। आइए 18 को फिर से एक उदाहरण के रूप में लें, इसके विभाजक खोजें, और इस गुण को प्रतिबिंबित करने के लिए उन्हें रंग दें।

इसलिए, उदाहरण के लिए, यदि j = 3, k = 6, और इसके विपरीत यदि j = 6, k = 3, तो इसका मतलब है कि 1 के अलावा, हम जिस सबसे छोटे j का उपयोग कर सकते हैं, वह 2 है, जो हमें सबसे बड़ा k देता है। संभव, n/2 (हमारे मामले में 9) । यह सही है:

• सम संख्याओं के लिए, इस स्थिति में सबसे बड़ा गुणनखंड बिल्कुल n के आधे के बराबर होगा;

• विषम संख्याओं के लिए: यदि हम n को 2 से विभाजित नहीं कर सकते (क्योंकि विषम होने पर हमें एक तर्कसंगत संख्या मिलेगी); इसका मतलब है कि हम केवल j > 2 का उपयोग कर सकते हैं, जो हमें हमेशा k < n/2 परिणाम देगा।

  
  

अंततः, केवल एक ही मामला है जिसमें j और k बराबर हो सकते हैं: जब n एक वर्ग संख्या है। उदाहरण के लिए, जब n = 36, एक संभावित कारक j = 6 एक अन्य कारक k = 6 उत्पन्न करेगा। हम इस मामले के बारे में बाद में कोड भाग में अधिक चर्चा करेंगे।

बेशक, ये अवधारणाएँ बहुत तुच्छ हैं, लेकिन वे हमारे समाधान में बहुत महत्वपूर्ण होंगी!

कोड

कोड गो में लिखा जाएगा, क्योंकि यह वास्तव में एक तेज़ भाषा है जो अभी भी पठनीयता का एक बड़ा स्तर बनाए रखती है। हम समाधान को दो भागों में विभाजित करेंगे: पहले, हम किसी संख्या के विभाजक खोजने के लिए एक फ़ंक्शन बनाएंगे, और फिर हम इसे त्रिकोणीय संख्याओं पर लागू करेंगे।

आइए पहले फ़ंक्शन देखें:

हम अपना फ़ंक्शन बनाते हैं जो एक पूर्णांक n स्वीकार करता है और पूर्णांकों की एक सरणी out है, जिसमें हमारे विभाजक शामिल होंगे। उसके बाद, हम तुच्छ कारकों को out हैं, अर्थात् 1 और n ।

फिर हम j 2 से n/2 तक लूप करना शुरू करते हैं (दूसरी संपत्ति से; यह भी ध्यान दें कि हमें n/2 में कोई दिलचस्पी नहीं है क्योंकि यदि n सम है, तो j = 2 द्वारा भाजक में k = n/2 जोड़ा जाएगा j = 2 पुनरावृत्ति: यही कारण है कि हम j<n/2 पर रुकते हैं न कि j≤ n/2 )।

इस तरह, हम केवल n के पहले भाग में विभाजकों की जांच कर सकते हैं, जिससे प्रक्रिया काफी तेज हो जाएगी।

प्रत्येक लूप में, हम 3 चीज़ें जाँचते हैं:

• तीसरा if कथन वास्तव में जाँच करता है कि क्या n%j==0 , दूसरे शब्दों में, यदि 0 ≡ n (mod j)। यदि ऐसा है, तो हमें एक कारक मिल गया है, और हम सूची में j जोड़ते हैं। हम n/j गणना करके और फिर अगले j पर जाकर इसके समकक्ष k को भी सूची में जोड़ सकते हैं;

• दूसरा यदि कथन जाँचता है कि क्या n एक वर्ग है, और इसलिए j n का मूल है। यदि ऐसा है, तो डुप्लिकेट से बचने के लिए, out में केवल एक विभाजक j जोड़ा जाएगा, और फिर एल्गोरिदम आगे बढ़ता है।

  
  

  मान लीजिए n = 36 : यदि यह छोटा ब्लॉक गायब होगा, तो तीसरा if स्टेटमेंट ट्रिगर हो जाएगा, out j = 6 और k = n/j = 36/6 = 6 प्राप्त होंगे, इस प्रकार, एक डुप्लिकेट बनाया जाएगा।

• पहला if कथन सबसे जटिल है: इसका उद्देश्य यह जांचना है कि क्या हम दोहराए जाने वाले jk जोड़े बनाना शुरू कर रहे हैं। यदि ऐसा है, तो हम तुरंत लूप को तोड़ सकते हैं, क्योंकि हमारा कारक पहले से ही out मौजूद होगा।

  
  

विशेष रूप से इस तीसरे बिंदु के बारे में, जाँच करने के लिए दो मामले हैं: क्या out[len(out)-1] == j या out[len(out)-2] == j

पहला मामला क्लासिक है: उदाहरण के लिए संख्या T₇ = 28 लें:

जब j = 7 , यह डाले गए अंतिम मान के बराबर होगा। इसलिए, हम लूप को तोड़ सकते हैं।

दूसरा मामला तभी घटित होता है जब हमें एक वर्ग n मिलता है। उदाहरण के लिए, 36 को फिर से लें:

जब j = 9 , यह n के वर्गमूल से पहले जोड़े गए अंतिम मान के बराबर होगा, जो केवल एक बार दिखाई देता है। इसलिए, इस बिंदु पर, हम लूप को तोड़ सकते हैं।

अंततः, हम आसानी से अपने विभाजक प्राप्त करने के लिए return out सकते हैं।

परिणाम लागू करना

अब चूँकि हमारे पास अपना कार्य है, हम इसे प्रत्येक त्रिकोणीय संख्या पर लागू कर सकते हैं। हम एक काउंटर c बनाने जा रहे हैं जो हमारे त्रिकोणीय संख्याओं के लिए जनरेटर के रूप में काम करेगा। हम गॉस समीकरण के साथ संबंधित त्रिकोणीय संख्या tn की गणना करते हैं और जांचते हैं कि इसमें कितने विभाजक हैं।

यदि यह 500 से अधिक है, तो हम परिणाम के रूप में वह tn लौटा देते हैं।

लेकिन...वहाँ एक पकड़ है!

ProjectEuler.net वास्तव में एक प्यारा प्रोजेक्ट है: गणित की पहेलियों और समस्याओं को प्रस्तुत करने के अलावा, उनका मुख्य ध्यान गणित के बारे में सीखना, सोचना और तर्क करना शुरू करने के लिए एक उपकरण प्रदान करना है।

और मुझे यह पसंद है: वे इतने प्रतिबद्ध हैं कि उनकी समस्याओं के लिए परिणाम और मार्गदर्शिकाएँ प्रकाशित करना वास्तव में निषिद्ध है (यह पहली 100 समस्याओं में से एक है, इसलिए मैं समझता हूँ कि इसकी अनुमति है)।

इसे देखते हुए, मुझे नहीं लगता कि केवल कॉपी-पेस्ट करने और उपलब्धि हासिल करने का समाधान देना उचित होगा। इस कारण से, मैं आपको वास्तविक समाधान नहीं दे रहा हूं: इसे स्वयं आज़माएं और मेरे से बेहतर एल्गोरिदम के साथ आने का प्रयास करें (ऐसे बहुत सारे हैं)। क्षमा करें दोस्तों! 😅

समय की जटिलता

मुझे विश्वास है कि कई बेहतर समाधान हैं क्योंकि मुझे लगता है कि यह एक बहुत ही भयानक शॉट है!

FindDivisor फ़ंक्शन रैखिक समय में चलता है: चूंकि यह उदाहरण n के आकार पर निर्भर करता है, और यह अधिकतम n/2 लूप पर भी चलता है; हम इसे O(n) मान सकते हैं।

हालाँकि, हमें पहले प्रत्येक त्रिकोणीय संख्या की गणना करनी चाहिए, जिसमें O(tn) समय भी लगता है, जहाँ tn परिणाम है (अंतिम जिसकी हम वास्तव में गणना करते हैं)। इसे देखते हुए, लगभग पूरे एल्गोरिदम की समय जटिलता O(tn*n) होनी चाहिए।

चूँकि tn तर्क या हमारा फ़ंक्शन बन जाता है, और हम इसके अंदर अधिकतम n/2 लूप चलाते हैं, हम समय जटिलता को O(tn*tn/2) = O(tn²/2) = O(tn²) के रूप में फिर से लिख सकते हैं। तो एक द्विघात समय समाधान , दुर्भाग्य से!

हालाँकि मुझे आश्चर्य हुआ कि भले ही एल्गोरिथ्म उस तरह की जटिलता के बारे में है, फिर भी यह बहुत तेज़ चलता है। मेरी मशीन पर परिणाम देने में (AMD Ryzen 5, औसत ck. 2700 MHz) 322.564227 एमएस लगा।

1000 विभाजकों से अधिक पहली त्रिकोणीय संख्या को खोजने का प्रयास करने में 3.827144472 सेकंड लगे, इसलिए यह स्पष्ट रूप से दिखाई दे रहा है कि समय की खपत तेजी से बढ़ रही है।

निष्कर्ष

आख़िरकार हमने इसे बना लिया! मुझे आशा है कि आप लोगों को लेख पसंद आया होगा, और मुझे आशा है कि आप इससे कुछ दिलचस्प सीख सकते हैं: यदि हां, तो कृपया एक या दो तालियाँ छोड़ें और लेख को किसी ऐसे व्यक्ति के साथ साझा करें जिसकी इस विषय में रुचि हो!

शानदार काम के लिए प्रोजेक्टयूलर को फिर से एक बड़ा धन्यवाद: मैं वास्तव में आपको सुझाव देना चाहता हूं कि आप जाएं और देखें कि वे क्या पेशकश कर सकते हैं; मुझे यकीन है कि आपको यह बेहद दिलचस्प लगेगा!

और हमेशा की तरह, पढ़ने के लिए धन्यवाद।

निकॉला