তোমাদের সেই ছোট্ট ছেলে পিনোকিওর কথা মনে আছে ??? যে কিনা একটি গ্রামে বাস করত আর মিথ্যে কথা বললেই যার নাক হয়ে যেত ইয়া লম্বা!
তো সেই পিনোকিও একদিন দুপুরবেলা ঘুরতে বেরোলো, কোথায় যাবে তার ঠিক নেই। মা নিষেধ করলেন বের হতে। কিন্তু পিনোকিও ঘুরতে যাবেই। তো যেতে যেতে সে অনেকদূর চলে এসেছে। সামনে পড়ল এক ঝর্ণা। এদিকে হাঁটতে হাঁটতে পিনোকিও বেশ ক্লান্ত। ঝর্ণার মিষ্টি পানি খেয়ে যেইনা একটু জিরোনোর জন্য বসেছে, অমনি যেন কোথা থেকে চার শিংয়ের এক গুঁফোদৈত্য এসে হাজির। দৈত্য বললো, এই ঝর্ণার পানি সে কাউকে ছুঁতেও দেয় না। কিন্তু আজ দুপুরে সে উদরপূর্তি করে ভাতঘুম দিতে গিয়েছিল। তাই পিনোকিও কোন দিক থেকে এসে পানি খেয়ে নিয়েছে সেটা সে বুঝতেই পারেনি। এখন ঘুম ভেঙ্গে দৈত্য তো বেজায় রাগ করে বসে আছে। আর পিনোকিওকে একটা শাস্তি দেওয়ার প্ল্যান করছে মনে মনে। বেচারা পিনোকিও ভাবছে, " ইশশ, কেনো যে মায়ের কথা অমান্য করে এখানে এলাম??? 😭"
গুঁফো বললো, সে গণিত খুউব্বই ভালোবাসে। তাকে একটা সংখ্যা দেওয়া হলে, সে চটপট ওইটার ফ্যাক্টোরিয়াল বের করে দিতে পারে। কিন্তু সংখ্যাটা আবার 20 এর বেশি হতে পারবে না! 😛
কিন্তু সে কয়েকদিন ধরে একটা সমস্যা সমাধান করতে চেষ্টা করছে। সে একটি সংখ্যার ফ্যাক্টোরিয়ালে অন্য আরেকটি সংখ্যা ঠিক কতবার আছে সেটা বের করতে চাচ্ছে। গুঁফোদৈত্য অনেক চেষ্টা করেও তার কোন সমাধানে আসতে পারছে না। তো পিনোকিওকে সেটা্র সমাধান দিতে হবে।
যারা "ঠিক কতবার আছে" এই কথাটা বুঝতে পারোনি, তারা একটা বিষয় লক্ষ্য করো, দৈত্য আসলে প্রথম সংখ্যার ফ্যাক্টোরিয়ালে দ্বিতীয় সংখ্যা কতবার আছে সেটা বের করতে চেয়ে আসলে তার সর্বোচ্চ পাওয়ার কত সেটাই বের করতে বলেছে।
পিনোকিও এটা শুনে তো খুব ভয় পেয়ে গেলো। কারণ দৈত্যের সমাধান করতে হলে তো এখন তাকে ফ্যাক্টোরিয়াল বের করে দিতে হবে, তারপর তাকে গুণে গুণে হিসাব করতে হবে ওই পিচ্চি সংখ্যাটা ঠিক কতবার আছে ফ্যাক্টোরিয়ালের ভেতর! 😩
সে আসলো তোমার কাছে। কারণ তুমি আবার কনটেস্ট-ফনটেস্ট না কি একটা করো। তাই তোমার কাছে এসব তো ডালভাত। তুমিও মহানন্দে লেগে গেলা পিনোকিওকে সাহায্য করতে, নাহলে দৈত্য যে তাকে ছাড়বে না বাপু।পিনোকিও একটা সংখ্যার প্রাইম ফ্যাক্টরগুলো বের করতে জানে। সে জানে যেকোন সংখ্যাকেই কতগুলি প্রাইম নাম্বারের পাওয়ারের গুণফল আকারে লিখা যায়। যেমন, আমরা চাচ্ছি, ১০কে প্রাইম ণাম্বারে ভাঙ্গাবো, আমরা তখন লিখব,
10 = 2^1 * 5^1
একইভাবে, 20 = 2^2 * 5^1
100 = 2^2 * 5^2
100 = 2^2 * 5^2
তো দেখা যাচ্ছে, আমরা একটি সংখ্যার প্রাইম ফ্যাক্টোরাইজেশন করতে হলে প্রথমে 2 থেকে শুরু করবো, যতক্ষণ 2 দ্বারা ভাগ করা যাচ্ছে ভাগ করতেই থাকব। একটা সময় আর 2 দ্বারা ভাগ করা না গেলে, তখন আমরা দেখবো সেটাকে 3 দ্বারা ভাগ করা যায় কিনা। তারপর 5, 7, 11, 13, 17, 19 ইত্যাদি ইত্যাদি।
এখন কথা হলো, ফ্যাক্টোরিয়ালে আরেকটা সংখ্যা কতবার থাকবে তার সাথে আবার এই প্রাইম ফ্যাক্টোরাইজেশনের সম্পর্ক কী? আছে, বলছি। 😋
আপাতত আমরা গুঁফোর সমস্যায় ফিরে যাই। খুব আশ্চর্যজনক হলেও সত্য যে, এই পাওয়ার বের করতে হলে আমাদের কোন ফ্যাক্টোরিয়ালই বের করা লাগবে না। আমাদের গুঁফোদৈত্যের সমাধান দিতে হলে আগে যে ব্যাপারটা মাথায় রাখা লাগবে তা হলো, যে সংখ্যাটি ফ্যাক্টোরিয়ালে কতবার আছে তা বের করতে বলা হয়েছে সেটি কি প্রাইম নাকি কম্পোজিট।
যদি প্রাইম হয়
সেটা আমরা খুব সহজেই বের করতে পারবো ফরাসী গণিতবিদ Legendre'র একটি চমৎকার সূত্র দিয়ে। তাঁর সূত্রমতে, একটি সংখ্যা n এর ফ্যাক্টোরিয়ালে আরেকটি প্রাইম p এর সর্বোচ্চ পাওয়ার কত হবে, সেটা বের করতে হলে আমরা শূন্য না হওয়া পর্যন্ত n-কে p দিয়ে ভাগ করতেই থাকব, করতেই থাকব। আর প্রতিবার ভাগফলগুলোর পূর্ণসাংখ্যিক মান নিয়ে যোগ করতে থাকব। এভাবে ভাগ করতে থাকলে এক সময় আমাদের n-এর মান শূন্য হবে, এভাবে যোগফলটাই হবে আমাদের সর্বোচ্চ পাওয়ার, hurrah !! 😄
একটা ছোট্ট উদাহরণ দিয়ে ব্যাখ্যা করা যাক।
ধরো, আমরা ১০ এর ফ্যাক্টোরিয়ালে ২ কতবার আছে সেটা বের করব। এখন আমরা এর ধাপগুলো দেখি।
ধাপ 1 : 10/2 = 5.0; আমরা নিবো 5. যোগফল = 5.
ধাপ 2 : 5/2 = 2.5; আমরা নিবো 2. যোগফল = 5+2 = 7.
ধাপ 3 : 2/2 = 1.0; আমরা নিবো 1. যোগফল = 7+1 = 8.
ধাপ 4 : 1/2 = 0.5; এখানে আমাদের থামতে হবে কারণ ভাজ্য 1, 2 এর চেয়ে ছোট, তাই ভাগফলের পূর্ণসাংখ্যিক মান হবে 0।
ধাপ 1 : 10/2 = 5.0; আমরা নিবো 5. যোগফল = 5.
ধাপ 2 : 5/2 = 2.5; আমরা নিবো 2. যোগফল = 5+2 = 7.
ধাপ 3 : 2/2 = 1.0; আমরা নিবো 1. যোগফল = 7+1 = 8.
ধাপ 4 : 1/2 = 0.5; এখানে আমাদের থামতে হবে কারণ ভাজ্য 1, 2 এর চেয়ে ছোট, তাই ভাগফলের পূর্ণসাংখ্যিক মান হবে 0।
তো আমরা পেলাম, 10! এ 2 আছে 8 বার। গাণিতিকভাবে, 10! = 3628800 আর 2^8 = 256. আমরা 10! কে 2^8 দ্বারা ভাগ করলে 14175 পাবো, যেটাকে আর 2 দ্বারা ভাগ করা যাচ্ছে না।
যদি কম্পোজিট হয়
এটা বের করাও খুব একটা কঠিন না। আমরা প্রথমে প্রাইম ফ্যাক্টোরাইজেশন দেখেছি, এক্ষেত্রে আমরা নিচের ধাপগুলো অনুসরণ করব।
ধাপ 1 : যে সংখ্যাটার পাওয়ার বের করতে বলবে সেই সংখ্যাটাকে আগে প্রাইম ফ্যাক্টরাইজ করবো। ধরে নেই, আমাকে 100! এর ভেতর 18 কতবার আছে সেটা বের করতে বলা হয়েছে। তো আগে আমরা 18 এর প্রাইম ফ্যাক্টোরাইজেশন করব এভাবে, 18 = 2 * 3^2.
ধাপ 2 : এবার প্রতিটি প্রাইম ফ্যাক্টর দিয়ে প্রথম সংখ্যাটাকে আগের সূত্রের মতোই ভাগ করতে থাকব। এভাবে ভাগ করলে আমরা 2 এর জন্য পাওয়ার পাবো 97 এবং 3 এর জন্য পাওয়ার পাবো 48.
ধাপ 3 : এবার প্রতি প্রাইমের পাওয়ারকে ওই প্রাইমের ফ্রিকোয়েন্সি দিয়ে ভাগ করবো। লক্ষ্য করলে দেখা যাবে যে, 18 এর প্রাইম ফ্যাক্টোরাইজেশনে 2 আছে 1 বার, তাই 2 এর ফ্রিকোয়েন্সি 1. একইভাবে 3 এর ফ্রিকোয়েন্সি হচ্ছে 2. আমরা ভাগ করলে 2 এর জন্য পাবো, 97/1 = 97 এবং 3 এর জন্য পাবো 48/2 = 24.
ধাপ 4 : সবশেষে আমরা সবগুলো ভাগফলের সর্বনিম্ন মানটা নিব। 97 এবং 24 এর মধ্যে সর্বনিম্ন হচ্ছে 24. সুতরাং, আমাদের সর্বোচ্চ পাওয়ার হবে 24.
আর এভাবেই পিনোকিও গুঁফোদৈত্যের সমস্যার সমাধান করে ফেলেছিলো। এখন সে তোমার কাছে আরেকটি আবদার নিয়ে এসেছে যে তাকে কিছু প্রোগ্রামিং সমস্যা দিতে হবে যেগুলো করে সে বেশ ভালভাবেই ব্যাপারটা আয়ত্ত্বে আনতে পারবে। গুঁফোদৈত্য তো 20 এর বেশি ফ্যাক্টোরিয়াল চিন্তা করতেই পারতো না, এখন পিনোকিও 20 এর চেয়ে অনেক বড় সংখ্যার ফ্যাক্টোরিয়ালের জন্যও এই হিসাব-নিকাশ করতে পারবে। আর সে এটাও বুঝতে পেরেছে যে, কখনো বড়দের কথার অবাধ্য হতে হয়না। 😊
রিলেটেড প্রবলেম :
রেফারেন্স লিংক :
হ্যাপী নাম্বার থিওরিং! 😉
No comments:
Post a Comment