দৈনিক কোডিং সমস্যা: ত্রিভুজাকার সংখ্যা এবং বড় ভাজক

অন্য সমস্যা সমাধানের সাথে সবাইকে স্বাগতম! আজ, আমরা ত্রিভুজাকার সংখ্যা এবং তাদের ভাজক সম্পর্কে কথা বলব: বিশেষ করে বিশাল সংখ্যা!

যদিও আমরা প্রকৃতিতে ত্রিভুজাকার সংখ্যার আমার দুর্দান্ত শৈল্পিক উপস্থাপনার প্রশংসা করতে পারি, আসুন আমাদের স্বাভাবিক দাবিত্যাগ করি:

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 টিরও বেশি ভাজক রয়েছে। প্রথম জিনিসগুলি প্রথমে, আসুন একটি ত্রিভুজাকার সংখ্যা কী এবং একটি ভাজক কী তা আরও ভালভাবে দেখে নেওয়া যাক।

ত্রিভুজাকার সংখ্যা

ত্রিভুজাকার সংখ্যা হল সংখ্যার একটি নির্দিষ্ট উপসেট যা একটি নির্দিষ্ট পর্যন্ত সমস্ত প্রাকৃতিক সংখ্যার যোগফল দ্বারা গঠিত হয়। এগুলিকে ত্রিভুজ বলা হয় কারণ আপনি সর্বদা একটি ত্রিভুজ হিসাবে তাদের সাজাতে পারেন । এখানে কিছু উদাহরণঃ:

উপরের চিত্রে, এটি ৩য়, ৪র্থ এবং ৫ম ত্রিভুজাকার সংখ্যা। সুতরাং, উদাহরণস্বরূপ, 3য় সংখ্যাটি 1+2+3 = 6 হিসাবে গঠিত হয়েছে, 4র্থটি 1+2+3+4 = 10 এবং আরও অনেক কিছু। সাধারণভাবে বলতে গেলে, nᵗʰ ত্রিভুজাকার সংখ্যা, Tₙ, এর সমান

এটি অবশ্যই, গণিতের সবচেয়ে বিখ্যাত সিরিজগুলির মধ্যে একটি, গাউস দ্বারাও উপস্থাপিত, যিনি বলেছিলেন যে ধারাবাহিক পূর্ণসংখ্যার যোগফল সমান:

তাই মূলত, আমরা যদি 3য় ত্রিভুজাকার সংখ্যা গণনা করতে চাই, উদাহরণস্বরূপ, আমরা কেবল 3*4/2 = 6 গণনা করি। একবার আমরা আমাদের সমাধান লিখতে শুরু করলে এটি খুবই সহায়ক হবে!

বিভাজক

একটি সংখ্যা n এর ভাজক (বা ফ্যাক্টর ) এর একটি সংজ্ঞা দিতে, এটি সত্যিই সহজ: এটি একটি সংখ্যা j যা আবার n দিতে অন্য পূর্ণসংখ্যা k দ্বারা গুণ করা যেতে পারে। উদাহরণস্বরূপ, 3 হল 18 এর ভাজক, কারণ আমরা আবার 18 পেতে 3 এবং 6 কে গুণ করতে পারি।

যাইহোক, 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- এর চেয়ে বড় একটি সংখ্যার কোনো ভাজক হতে পারে না। এই বুঝতে বেশ সহজ. প্রথম প্রপার্টি থেকে, আমরা জানি যে ফ্যাক্টরগুলো কোনো না কোনোভাবে 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 তৈরি করবে। আমরা কোড অংশে পরে এই ক্ষেত্রে আরও আলোচনা করব।

এই ধারণাগুলি অবশ্যই খুব তুচ্ছ, তবে সেগুলি আমাদের সমাধানে খুব গুরুত্বপূর্ণ হবে!

কোড

কোডটি Go তে লেখা হবে, কারণ এটি সত্যিই একটি দ্রুত ভাষা যা এখনও পাঠযোগ্যতার একটি দুর্দান্ত স্তর বজায় রাখে। আমরা সমাধানটিকে দুটি ভাগে ভাগ করব: প্রথমত, আমরা একটি সংখ্যার ভাজক খুঁজে বের করার জন্য একটি ফাংশন তৈরি করব, এবং তারপরে আমরা এটি ত্রিভুজাকার সংখ্যাগুলিতে প্রয়োগ করব ।

আসুন প্রথমে ফাংশনটি দেখি:

আমরা আমাদের ফাংশন তৈরি করি যা একটি পূর্ণসংখ্যা n গ্রহণ করে এবং পূর্ণসংখ্যার একটি অ্যারে out করে, যাতে আমাদের ভাজক থাকবে। এর পরে, আমরা তুচ্ছ ফ্যাক্টরগুলির সাথে out করি, যথা 1 এবং n নিজেই।

তারপরে আমরা 2 থেকে n/2 থেকে j লুপ করা শুরু করি (দ্বিতীয় বৈশিষ্ট্য থেকে; এছাড়াও মনে রাখবেন যে আমরা n/2 নিজেই আগ্রহী নই কারণ n জোড় হলে, k = n/2 ভাজকের সাথে j = 2 দ্বারা যোগ করা হবে j = 2 পুনরাবৃত্তি: এই কারণে আমরা j<n/2 এ থামি এবং j≤ n/2 নয়)।

এইভাবে, আমরা কেবলমাত্র n এর প্রথমার্ধে ভাজক পরীক্ষা করতে পারি, প্রক্রিয়াটিকে কিছুটা দ্রুততর করে।

প্রতিটি লুপে, আমরা 3টি জিনিস পরীক্ষা করি:

• তৃতীয় if স্টেটমেন্টটি আসলে পরীক্ষা করে যদি n%j==0 , অন্য কথায়, যদি 0 ≡ n (mod j)। যদি তাই হয়, আমরা একটি ফ্যাক্টর খুঁজে পেয়েছি, এবং আমরা তালিকায় j যোগ করি। n/j গণনা করে এবং তারপরে পরবর্তী j এ যাওয়ার মাধ্যমে আমরা তালিকায় এর প্রতিরূপ k যুক্ত করতে পারি;

• দ্বিতীয় if স্টেটমেন্ট n একটি বর্গ কিনা তা পরীক্ষা করে এবং তাই j হল n এর মূল। যদি তাই হয়, শুধুমাত্র একটি ভাজক j যোগ করা হবে out , তাই ডুপ্লিকেট এড়াতে, এবং তারপর অ্যালগরিদম এগিয়ে যায়।

  
  

  ধরুন 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, avg. ck. 2700 MHz) 322.564227 ms লেগেছে।

1000 ভাজক অতিক্রমকারী প্রথম ত্রিভুজাকার সংখ্যাটি খুঁজে বের করার চেষ্টা করতে 3.827144472 সেকেন্ড সময় লেগেছে, তাই এটি স্পষ্টভাবে দৃশ্যমান যে সময় খরচ দ্রুত বৃদ্ধি পাচ্ছে।

উপসংহার

আমরা অবশেষে এটা করেছি! আমি আশা করি আপনি নিবন্ধটি উপভোগ করেছেন, এবং আমি আশা করি আপনি এটি থেকে আকর্ষণীয় কিছু নিতে পারেন: যদি তাই হয়, দয়া করে একটি বা দুটি হাততালি দিন এবং এই বিষয়ে আগ্রহী এমন কারো সাথে নিবন্ধটি ভাগ করুন!

চমৎকার কাজের জন্য আবার প্রজেক্টইউলারের কাছে একটি বড় চিৎকার: আমি সত্যিই আপনাকে পরামর্শ দিতে চাই যে তারা কী অফার করতে পারে তা দেখুন; আমি নিশ্চিত আপনি এটি সুপার আকর্ষণীয় পাবেন!

এবং সবসময় হিসাবে, পড়ার জন্য ধন্যবাদ.

নিকোলা