All posts filed under “নাম্বার থিওরী

comment 0

পুর্ণ সংখ্যার সেট বিট নির্ণয়

কোন একটি সংখ্যাকে বাইনারিতে প্রকাশ করলে সেখানে শুধুমাত্র ০ অথবা ১ থাকে । একটি বাইনারি সংখ্যায় কতগুলো ১ আছে, তার মানই সংখ্যাটির সেট বিট । সেট বিট কাউন্ট করার বেশ কিছু উপায় আছে । এর মধ্যে দুটো উপায় নিয়ে আমি আলোচনা করবো ।

মেথড ০১ঃ (সিম্পল মেথড)
এটি খুবই সহজ একটি উপায় । একটি সংখ্যার সবগুলো বিট পর্যায়ক্রমে চেক করতে হবে । যদি নির্দিস্ট বিটটি সেট অবস্থায় থাকে । তাহলে সেট বিট কাউন্টারের মান ১ বাড়াতে হবে । কোন একটি বিট সাধারণত দুটো অবস্থায় থাকতে পারে – সেট অবস্থা আর ক্লিয়ার অবস্থা । যদি বিটটি ০ শূন্য তাহলে বলা হবে ক্লিয়ায় মোড আর ১ হলে বলা হবে সেট মোড । তুমি ডেসিম্যাল টু বাইনারি কনভার্সন জেনে থাকলে বিট চেক করা তোমার জন্য কোন কাজই না । কোন পূর্ণ সংখ্যাকে ২ দিয়ে ভাগ দিলে হয় ভাগশেষ ১ থাকবে না হয় ০ থাকবে । ২ দিয়ে বারবার ভাগ করেই বাইনারি টু ডেসিম্যাল কনভার্সন করা হয় ।

comment 0

পূর্ণ সংখ্যার প্রাইম ফ্যাক্টরাইজেশন

নাম্বার থিওরীতে কোন একটি ধনাত্মক সংখ্যার মৌলিক গুণনীয়ক বা প্রাইম ফ্যাক্টর হলো এমন কতগুলো মৌলিক সংখ্যা যা ঐ সংখ্যাটিকে সঠিকভাবে ভাগ করে । মানে, যে সকল প্রাইম নাম্বার দিয়ে ঐ সংখ্যাটিকে ভাগ দিলে ভাগশেষ শূন্য হয়, তারাই সংখ্যাটির মৌলিক গুণনীয়ক। মৌলিক গুণনীয়ক নির্ণয়ের এ প্রক্রিয়াকে বলা হয় – ইন্টিজার ফ্যাক্টরাইজেশন । ফান্ডামেন্টাল এরিথমেটিক থিওরেম অনুযায়ী প্রত্যেকটি ধনাত্মক সংখ্যার একটি সিঙ্গেল এবং ইউনিক প্রাইম ফ্যাক্টরাইজেশন থাকা আবশ্যিক ।

comment 0

মডুলার এরিথমেটিক, বিগ মড, মডুলার ইনভার্স, এক্সটেন্ডেড ইউক্লিড, চাইনিজ রিমেইন্ডার থিওরেম, প্রাইমারিলিটি টেস্টিং

Big Mod ফাংশনের কোড: [code language=”C”] #define ll long long ll bigmod(ll b, ll p, ll m) { ll ret; if(p==0) return 1; if(p%2==0){ ret=bigmod(b, p/2, m); return ((ret%m)*(ret%m)%m); } else return ((b%m)*(bigmod(b, p-1, m)%m)%m); }[/code] Extended Euclid ফাংশনের কোড: [code language=”C”]int extendedEulid(int a, int b) { if(b==0) { x=1; y=0; d=a; /// some extensions return a; } int ret = extendedEulid(b, a%b); /// GCD function int x1 = y; /// some extensions int y1 = x – (a/b) *y; x = x1; y = y1; return ret; }[/code] রেফারেন্স লিঙ্কঃ ১. ভাগশেষের গণিত (মডুলার অ্যারিথমেটিক + বিগ মড) ২. Extended Euclidean…

comment 0

ইউলার ফাই ফাংশন 

নাম্বার থিওরীর বেশ মজার একটি টপিকস হলো ইউলার ফাই ফাংশন। নাম্বার থিওরী রিলেটেড প্রবলেম সলভ করতে গেলে দেখবে প্রায়ই এটি খুব কাজে লাগছে। ইউলার ফাই ফাংশন খুবই সহজ একটি কনসেপ্ট। একটি সীমার মাঝে কয়টি রিলেটিভলি প্রাইম আছে সেটা খুজে বের করাই এর কাজ। ইউলার ফাইয়ের সবচে মজার পার্ট হলো এর বেশ কিছু ইন্টারেস্টিং প্রপার্টিজ আছে আর সিভ অফ এরাটস্থেনিজ এলগরিদম জানা থাকলে এর কোডিং করাটাও বেশ ইজি। ইউলার ফাই বা ইউলার টশিয়েন্ট ফাই মূলত একটি ফর্মুলা। লেখাটির পুরো অংশ জুড়ে আমরা ঐ ফর্মুলাটি বুঝার চেষ্টা করবো। ফর্মুলাটি হলো –

comment 0

প্রাইমারিলিটি টেস্টিং (সিভ অব এরাটস্থেনিজ)

সংখ্যাতত্ত্বের অসাধারণ সৌন্দর্য্য আর বহুমাত্রিক ব্যবহারের কারণে প্রাইম নাম্বার গণিত আর কম্পিউটার বিজ্ঞানে বেশ আলোচিত একটি বিষয়। সেই ক্লাস টু থেকেই মৌলিক সংখ্যা সম্পর্কে আমরা জানি। একদম প্রাইমারি স্কুলের সময়ে আমরা প্রাইম নাম্বার সম্পর্কে যা শিখেছি তা হলো এরকম – যে সকল ধনাত্মক পূর্ণ সংখ্যাকে ১ ও ঐ সংখ্যাটি ব্যতীত অন্য কোন সংখ্যা দিয়ে নিঃশেষে ভাগ করা যায় না, সেসব সংখ্যাই হল প্রাইম সংখ্যা। যেমন – ১, ৩, ৫, ৭, ১১… ইত্যাদি। প্রাইম সংখ্যার অন্যতম মৌলিক বৈশিষ্ট্য হলো এর প্রকৃত ভাজক সংখ্যা হবে স্ট্রিক্টলি দুটো। ঠিক এই কারণেই ১ কে প্রাইম নাম্বার হিসেবে কাউন্ট করা হয় না। কারণ ১ ব্যতীত এর অন্য কোন ভাজক নেই। অন্যদিকে ৫ এর ভাজক দুটি (১ ও ৫) বিধায় ৫ একটি প্রাইম সংখ্যা । ৬ প্রাইম সংখ্যা না কারণ ৬ এর ভাজক ৪ টি (১, ২, ৩, ৬)।

comment 0

প্রবলেম সলভিং – এলসিএম (১)

টপিকঃ LCM

প্রোগ্রামিং প্রবলেম সলভিংয়ে এলসিএম বেশ কমন। সাধারণত দুটি সংখ্যা দেয়া থাকে এবং এদের এলসিএম বের করতে হয়। এখানে যে প্রবলেমটি নিয়ে আলোচনা করা হয়েছে, এতে দুটি সংখ্যার ল.সা.গু(LCM) এবং সংখ্যা দুটির যেকোন একটি দেয়া আছে, অপর সংখ্যাটি বের করতে হবে।

প্রথমে কিভাবে দুটি সংখ্যার এলসিএম নির্ণয় করতে হয় দেখা যাক-

(এলসিএম নির্ণয় করার জন্য একেকজন একেক নিয়ম অনুসরণ করে থাকে। আমরা নিচের নিয়মে করবো কারণ এতে গ.সা.গু নির্ণয় করাও শিখে ফেলা যাবে।)