Phương pháp đếm số bội, ước của một số trên một khoảng xác định

0. Giới thiệu#

Trong quá trình giải một số bài toán toán học, đặc biệt ở nội dung số học, ta thường gặp các bài toán yêu cầu đếm số ước hoặc số bội của một số trên một khoảng xác định. Nếu thực hiện bằng cách liệt kê trực tiếp các giá trị trong khoảng, việc tính toán sẽ tốn nhiều thời gian và dễ phát sinh sai sót, nhất là khi khoảng xét lớn. Vì vậy, bài viết này trình bày một phương pháp tiếp cận hiệu quả dựa trên việc sử dụng máy tính cầm tay, kết hợp với các lập luận và chứng minh toán học cơ bản, nhằm giúp tính nhanh và chính xác số ước, số bội của một số trên một khoảng xác định.

Để thuận tiện, trong bài viết này chúng ta quy ước như sau:

$\displaystyle \left\lfloor x \right\rfloor$ là phần nguyên của $\displaystyle x$ , tương đương với $\text{Int(x)}$ trong máy tính cầm tay.

$\displaystyle \lambda$ là một số nguyên dương rất lớn. Khi bấm máy, ta thay $\displaystyle \lambda$ bằng $\displaystyle 18^{11}$ hoặc một số khác đủ lớn.

1. Đếm số bội#

Đề bài#

Cho ba số nguyên dương $\displaystyle n, L, R$ thỏa mãn $\displaystyle L \le R$ . Đếm số bội của $\displaystyle n$ trong đoạn $\displaystyle \left[ L; R \right]$ .

Cách giải#

Ta biết rằng các bội của $\displaystyle n$ có dạng $\displaystyle kn$ , với $k$ là số nguyên dương bất kỳ.

Như vậy, trong đoạn $\displaystyle \left[ 1; qn + r \right] \ \left( q \in \mathbb{N}, \ 0 \le r < n \right)$ có đúng $\displaystyle q$ bội của $\displaystyle n$ là $\displaystyle n, 2n, 3n, \dots, qn$

Lại có $\displaystyle q = \left\lfloor \dfrac{qn + r}{n} \right\rfloor$

Vậy trong đoạn $\displaystyle \left[ 1; x \right] \ \left( x \in \mathbb{N} \right)$ có đúng $\displaystyle \left\lfloor \dfrac{x}{n} \right\rfloor$ bội của $\displaystyle n$

Mặt khác, ta có $\displaystyle \left[ L; R \right] = \left[ 1; R \right] \backslash \left[ 1; L - 1 \right]$

Vậy số bội của $\displaystyle n$ trong $\displaystyle \left[ L; R \right]$ là $\displaystyle M = \left\lfloor \dfrac{R}{n} \right\rfloor - \left\lfloor \dfrac{L - 1}{n} \right\rfloor$

2. Đếm số ước#

Đề bài#

Cho ba số nguyên dương $\displaystyle n, L, R$ thỏa mãn $\displaystyle L \le R$ . Đếm số ước của $\displaystyle n$ trong đoạn $\displaystyle \left[ L; R \right]$ .

Cách giải#

Xét hàm $\displaystyle r(x) = \frac{n}{x} - \left\lfloor \frac{n}{x} \right\rfloor$ . Ta có:

$\displaystyle r(x) = 0$ nếu $n$ chia hết cho $x$
$\displaystyle r(x) \in \left(0; 1\right)$ nếu $n$ không chia hết cho $x$

Xét hàm $\displaystyle f(x) = \sqrt[\lambda]{x}$ . Ta có:

$\displaystyle f(x) = 0$ nếu $x = 0$
$\displaystyle f(x) \approx 1$ nếu $0 < x < 1$

Từ hai nhận xét trên, ta có:

$\displaystyle \sqrt[\lambda]{\frac{n}{x} - \left\lfloor \frac{n}{x} \right\rfloor} = 0$ nếu $n$ chia hết cho $x$
$\displaystyle \sqrt[\lambda]{\frac{n}{x} - \left\lfloor \frac{n}{x} \right\rfloor} \approx 1$ nếu $n$ không chia hết cho $x$

Xét tổng $\displaystyle S = \sum_{x = L}^{R} \sqrt[\lambda]{\frac{n}{x} - \left\lfloor \frac{n}{x} \right\rfloor}$

Mỗi số nguyên $x$ sao cho $n$ không chia hết cho $x$ đóng góp xấp xỉ $1$ đơn vị vào tổng $S$ , trong khi mỗi số nguyên $x$ sao cho $n$ chia hết cho $x$ đóng góp $0$ đơn vị vào tổng $S$ . Vậy $S$ xấp xỉ bằng số các số nguyên $x$ sao cho $x$ không phải là ước của $n$ .

Mà trong đoạn $\left[ L; R \right]$ có $R - L + 1$ số nguyên.

Vậy số ước của $n$ trong $\left[ L; R \right]$ là $\displaystyle D \approx R - L + 1 - S$

Áp dụng#

Có bao nhiêu cấp số cộng có ít nhất $20$ số hạng thỏa mãn các số hạng của cấp số cộng là các số tự nhiên, công sai của cấp số cộng bằng $2$ và tổng tất cả các số hạng bằng $6300$ ?

Giả sử cấp số cộng này có $n$ số hạng, số hạng đầu tiên là $u_1$ .

Theo đề bài ta có tổng các số hạng bằng $6300$ , nói cách khác:

\begin{aligned} & 6300 = \frac{n\left[2u_1 + \left(n-1\right)d\right]}{2} \\ \iff & 6300 = \frac{2n\left(u_1 + n - 1\right)}{2} \\ \iff & 6300 = n\left(u_1 + n - 1\right) \\ \iff & \frac{6300}{n} = u_1 + n - 1 \\ \iff & u_1 = \frac{6300}{n} - n + 1 \end{aligned}

Các số hạng của cấp số cộng là số tự nhiên khi và chỉ khi $u_1$ là số tự nhiên, tức là $u_1$ nguyên và $u_1 \ge 0$ .

$u_1$ là số nguyên khi và chỉ khi $6300$ chia hết cho $n$ , tức là $n$ là ước của $6300$ .

\begin{aligned} u_1 \ge 0 \iff & \frac{6300}{n} - n + 1 \ge 0 \\ \iff & \frac{6300 - n^2 + n}{n} \ge 0 \\ \iff & -n^2 + n + 6300 \ge 0 \\ \iff & -78{,}87 \le n \le 79{,}87 \end{aligned}

Mà theo đề bài ta có $n \ge 20$ .

Với mỗi giá trị $n$ thỏa mãn điều kiện, ta xác định được đúng một cấp số cộng tương ứng thỏa mãn yêu cầu bài toán.

Vậy bài toán trở thành: Tìm số ước của $6300$ trong đoạn $\left[20; 79\right]$ .

Bấm máy $\displaystyle\left(79 - 20 + 1\right) - \sum_{x = 20}^{79}\left(\sqrt[18^{11}]{\frac{6300}{x} - \text{Int}\left(\frac{6300}{x}\right)}\right)$ , ta được kết quả là $14$ .

Vậy có $14$ cấp số cộng thỏa mãn yêu cầu bài toán.