ভাজকের সংখ্যা / ভাজকের যোগফল#
এই আর্টিকেলে আমরা আলোচনা করব কীভাবে একটি প্রদত্ত সংখ্যা $n$-এর ভাজকের সংখ্যা $d(n)$ এবং ভাজকের যোগফল $\sigma(n)$ গণনা করতে হয়।
ভাজকের সংখ্যা#
এটি স্পষ্ট হওয়া উচিত যে একটি ভাজক $d$-এর মৌলিক উৎপাদক বিভাজন $n$-এর মৌলিক উৎপাদক বিভাজনের একটি উপসেট হতে হবে, যেমন $6 = 2 \cdot 3$ হলো $60 = 2^2 \cdot 3 \cdot 5$-এর একটি ভাজক। তাই আমাদের শুধু $n$-এর মৌলিক উৎপাদক বিভাজনের সকল ভিন্ন উপসেট খুঁজতে হবে।
সাধারণত $x$ টি উপাদানবিশিষ্ট সেটের উপসেটের সংখ্যা $2^x$। তবে সেটে পুনরাবৃত্ত উপাদান থাকলে এটি আর সত্য নয়। আমাদের ক্ষেত্রে $n$-এর মৌলিক উৎপাদক বিভাজনে কিছু মৌলিক গুণনীয়ক একাধিকবার আসতে পারে।
যদি একটি মৌলিক গুণনীয়ক $p$ $n$-এর মৌলিক উৎপাদক বিভাজনে $e$ বার আসে, তাহলে আমরা উপসেটে $p$ গুণনীয়কটি $e$ বার পর্যন্ত ব্যবহার করতে পারি। যার মানে আমাদের $e+1$ টি পছন্দ আছে।
তাই যদি $n$-এর মৌলিক উৎপাদক বিভাজন $p_1^{e_1} \cdot p_2^{e_2} \cdots p_k^{e_k}$ হয়, যেখানে $p_i$ স্বতন্ত্র মৌলিক সংখ্যা, তাহলে ভাজকের সংখ্যা হলো:
$$d(n) = (e_1 + 1) \cdot (e_2 + 1) \cdots (e_k + 1)$$এটি নিম্নরূপে ভাবা যায়:
যদি শুধু একটি স্বতন্ত্র মৌলিক ভাজক থাকে $n = p_1^{e_1}$, তাহলে স্পষ্টতই $e_1 + 1$ টি ভাজক আছে ($1, p_1, p_1^2, \dots, p_1^{e_1}$)।
যদি দুটি স্বতন্ত্র মৌলিক ভাজক থাকে $n = p_1^{e_1} \cdot p_2^{e_2}$, তাহলে আপনি সকল ভাজক একটি টেবিলের আকারে সাজাতে পারেন।
তাই ভাজকের সংখ্যা সহজেই $(e_1 + 1) \cdot (e_2 + 1)$।
- দুইয়ের বেশি স্বতন্ত্র মৌলিক গুণনীয়ক থাকলেও একই যুক্তি দেওয়া যায়।
long long numberOfDivisors(long long num) {
long long total = 1;
for (int i = 2; (long long)i * i <= num; i++) {
if (num % i == 0) {
int e = 0;
do {
e++;
num /= i;
} while (num % i == 0);
total *= e + 1;
}
}
if (num > 1) {
total *= 2;
}
return total;
}ভাজকের যোগফল#
আমরা আগের অনুচ্ছেদের একই যুক্তি ব্যবহার করতে পারি।
- যদি শুধু একটি স্বতন্ত্র মৌলিক ভাজক থাকে $n = p_1^{e_1}$, তাহলে যোগফল:
- যদি দুটি স্বতন্ত্র মৌলিক ভাজক থাকে $n = p_1^{e_1} \cdot p_2^{e_2}$, তাহলে আমরা আগের মতোই টেবিল তৈরি করতে পারি। পার্থক্য শুধু এই যে এখন আমরা উপাদান গণনার বদলে যোগফল গণনা করতে চাই। দেখা সহজ যে প্রতিটি কম্বিনেশনের যোগফল এভাবে প্রকাশ করা যায়:
- সাধারণভাবে, $n = p_1^{e_1} \cdot p_2^{e_2} \cdots p_k^{e_k}$-এর জন্য আমরা সূত্র পাই:
long long SumOfDivisors(long long num) {
long long total = 1;
for (int i = 2; (long long)i * i <= num; i++) {
if (num % i == 0) {
int e = 0;
do {
e++;
num /= i;
} while (num % i == 0);
long long sum = 0, pow = 1;
do {
sum += pow;
pow *= i;
} while (e-- > 0);
total *= sum;
}
}
if (num > 1) {
total *= (1 + num);
}
return total;
}গুণনমূলক ফাংশন#
একটি গুণনমূলক ফাংশন হলো এমন একটি ফাংশন $f(x)$ যা পূরণ করে
$$f(a \cdot b) = f(a) \cdot f(b)$$যদি $a$ এবং $b$ সহমৌলিক হয়।
$d(n)$ এবং $\sigma(n)$ উভয়ই গুণনমূলক ফাংশন।
গুণনমূলক ফাংশনের বিভিন্ন আকর্ষণীয় বৈশিষ্ট্য আছে, যা সংখ্যাতত্ত্বের সমস্যায় অত্যন্ত উপকারী হতে পারে। উদাহরণস্বরূপ, দুটি গুণনমূলক ফাংশনের ডিরিশলে কনভলিউশনও গুণনমূলক।