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

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

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

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

ببین، یه نکته‌ی خیلی ساده ولی مهم اینه که وقتی یه عدد $d$ مقسوم‌علیه $n$ باشه، عوامل اولِ $d$ حتماً یه زیرمجموعه‌ای از عوامل اولِ $n$ هستن. مثلاً $6 = 2 \cdot 3$ رو در نظر بگیر که مقسوم‌علیه $60 = 2^2 \cdot 3 \cdot 5$ هست. همونطور که می‌بینی، عوامل اول ۶ (یعنی ۲ و ۳) توی عوامل اول ۶۰ هم پیدا میشن. پس کارمون این میشه که همه‌ی زیرمجموعه‌های ممکن از عوامل اول $n$ رو پیدا کنیم.

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

فرض کن یه عامل اول مثل $p$، به تعداد $e$ بار توی تجزیه‌ی $n$ اومده. این یعنی برای ساختن یه مقسوم‌علیه، می‌تونیم از این عامل $p$ اصلاً استفاده نکنیم (توان صفر)، یا یه بار استفاده کنیم (توان یک)، یا دو بار، ... تا $e$ بار. پس در کل برای عامل $p$، ما $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) هست که اگه روی دو تا تابع ضربی انجامش بدی، نتیجه‌اش بازم یه تابع ضربی میشه.

چند تا مسئله برای تمرین