پرش به محتویات

تعداد مقسوم‌علیه‌ها / مجموع مقسوم‌علیه‌ها

در این مقاله، نحوه‌ی محاسبه‌ی تعداد مقسوم‌علیه‌ها $d(n)$ و مجموع مقسوم‌علیه‌ها $\sigma(n)$ برای یک عدد داده‌شده‌ی $n$ را بررسی می‌کنیم.

تعداد مقسوم‌علیه‌ها

باید واضح باشد که تجزیه‌ی عامل‌های اول یک مقسوم‌علیه $d$ باید زیرمجموعه‌ای از تجزیه‌ی عامل‌های اول عدد $n$ باشد. برای مثال، $6 = 2 \cdot 3$ مقسوم‌علیه عدد $60 = 2^2 \cdot 3 \cdot 5$ است. بنابراین کافی است تمام زیرمجموعه‌های مختلف از تجزیه‌ی عامل‌های اول $n$ را پیدا کنیم.

معمولاً برای یک مجموعه با $x$ عضو، تعداد زیرمجموعه‌ها $2^x$ است. اما اگر در مجموعه اعضای تکراری وجود داشته باشد، این موضوع دیگر صادق نیست. در مورد ما، ممکن است برخی از عوامل اول چندین بار در تجزیه‌ی $n$ ظاهر شوند.

اگر یک عامل اول $p$ به تعداد $e$ بار در تجزیه‌ی $n$ ظاهر شود، آنگاه می‌توانیم از عامل $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}$، آنگاه می‌توانید تمام مقسوم‌علیه‌ها را به شکل یک جدول مرتب کنید.

$$\begin{array}{c|ccccc} & 1 & p_2 & p_2^2 & \dots & p_2^{e_2} \\\\\hline 1 & 1 & p_2 & p_2^2 & \dots & p_2^{e_2} \\\\ p_1 & p_1 & p_1 \cdot p_2 & p_1 \cdot p_2^2 & \dots & p_1 \cdot p_2^{e_2} \\\\ p_1^2 & p_1^2 & p_1^2 \cdot p_2 & p_1^2 \cdot p_2^2 & \dots & p_1^2 \cdot p_2^{e_2} \\\\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\\\ p_1^{e_1} & p_1^{e_1} & p_1^{e_1} \cdot p_2 & p_1^{e_1} \cdot p_2^2 & \dots & p_1^{e_1} \cdot p_2^{e_2} \\\\ \end{array}$$

پس بدیهی است که تعداد مقسوم‌علیه‌ها $(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}$، آنگاه مجموع برابر است با:
$$1 + p_1 + p_1^2 + \dots + p_1^{e_1} = \frac{p_1^{e_1 + 1} - 1}{p_1 - 1}$$
  • اگر دو مقسوم‌علیه اول متمایز وجود داشته باشد، یعنی $n = p_1^{e_1} \cdot p_2^{e_2}$، می‌توانیم همان جدول قبل را بسازیم. تنها تفاوت این است که این بار به جای شمردن اعضا، می‌خواهیم مجموع آن‌ها را محاسبه کنیم. به راحتی می‌توان دید که مجموع تمام مقسوم‌علیه‌ها را می‌توان به صورت زیر بیان کرد:
$$\left(1 + p_1 + p_1^2 + \dots + p_1^{e_1}\right) \cdot \left(1 + p_2 + p_2^2 + \dots + p_2^{e_2}\right)$$
$$ = \frac{p_1^{e_1 + 1} - 1}{p_1 - 1} \cdot \frac{p_2^{e_2 + 1} - 1}{p_2 - 1}$$
  • به طور کلی، برای $n = p_1^{e_1} \cdot p_2^{e_2} \cdots p_k^{e_k}$ فرمول زیر را به دست می‌آوریم:
$$\sigma(n) = \frac{p_1^{e_1 + 1} - 1}{p_1 - 1} \cdot \frac{p_2^{e_2 + 1} - 1}{p_2 - 1} \cdots \frac{p_k^{e_k + 1} - 1}{p_k - 1}$$
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;
}

توابع ضربی

یک تابع ضربی (multiplicative function)، تابعی مانند $f(x)$ است که در شرط زیر صدق می‌کند:

$$f(a \cdot b) = f(a) \cdot f(b)$$

اگر $a$ و $b$ نسبت به هم اول باشند.

هر دو تابع $d(n)$ و $\sigma(n)$ ضربی هستند.

توابع ضربی دارای ویژگی‌های جالب و متنوعی هستند که می‌توانند در مسائل نظریه اعداد بسیار مفید باشند. برای مثال، کانولوشن دیریکله (Dirichlet convolution) دو تابع ضربی نیز، خود یک تابع ضربی است.

مسائل تمرینی