Đến nội dung

Hình ảnh

Tìm $n\in \mathbb{N}(n>0)$ là hợp số để $S(n)-P(n)$ đạt GTNN

- - - - -

  • Please log in to reply
Chủ đề này có 6 trả lời

#1
Lemonjuice

Lemonjuice

    Trung sĩ

  • Thành viên
  • 118 Bài viết

Cho $n$ là một số nguyên dương; ký hiệu $S(n)$ là số các số nguyên tố không vượt quá $n$. Ký hiệu $P(n)$ là số ước nguyên tố của $n$. Tìm $n$ để $S(n)-P(n)$ đạt giá trị nhỏ nhất biết $n$ là hợp số và cho biết giá trị nhỏ nhất đó là bao nhiêu.

 

Tổng quát hơn nhé  :D : Tìm tất cả các số n để $S(n)-P(n)=1$


Bài viết đã được chỉnh sửa nội dung bởi Lemonjuice: 22-05-2021 - 21:30


#2
perfectstrong

perfectstrong

    $LOVE(x)|_{x =\alpha}^\Omega=+\infty$

  • Quản lý Toán Ứng dụng
  • 4991 Bài viết

Hàm $S(n)$ của bạn là hàm đếm số nguyên tố (prime-counting function). Có nhiều nghiên  cứu nổi tiếng về vấn đề này rồi :D

https://primes.utm.edu/howmany.html

 

Bài toán này mình chỉ mới có ý tưởng này:

Sử dụng phân tích nguyên tố của $n$ :

\[n = p_1^{{a_1}}p_2^{{a_2}}...p_k^{{a_k}}\]

Ta thấy ngay $P(n)=k$. Còn $S(n)$ mặc dù không biết nhưng ta có nhận xét như sau: $S(n)$ là hàm tăng.

Vì thế, với mỗi số mũ $a_i \ge 2$, nếu thay $a_i = 1$ thì $n$ sẽ giảm xuống, nên $S(n)$ giảm, nhưng $P(n)$ không giảm. Do đó hiệu số $A(n)=S(n)-P(n)$ giảm.

Vậy nên để $A(n)$ nhỏ nhất, ta chỉ cần quan tâm các hợp số không chia hết cho mọi bình phương của nguyên tố: $n=p_1 p_2 ... p_k$

 

Giờ chúng ta đi chặn giá trị của $A(n)$.

Mặt khác, nếu $p$ là ước nguyên tố của $n$ thì $p$ sẽ đươc đếm trong $S(n)$. Do đó $S(n) \ge P(n) \Rightarrow A(n) \ge 0$.


Luôn yêu để sống, luôn sống để học toán, luôn học toán để yêu!!! :D
$$\text{LOVE}\left( x \right)|_{x = \alpha}^\Omega = + \infty $$
I'm still there everywhere.

#3
perfectstrong

perfectstrong

    $LOVE(x)|_{x =\alpha}^\Omega=+\infty$

  • Quản lý Toán Ứng dụng
  • 4991 Bài viết

Nối tiếp ý tưởng giữ nguyên $P(n)$ và hạ $S(n)$ thì có thể thấy nếu trong phân tích nguyên tố $p_1p_2...p_k$ của $n$ (giả sử $p_i$ tăng dần), nếu có $p_i$ và $p_{i+1}$ không phải hai số nguyên tố liên tiếp thì có thể thay $p_{i+1}$ bằng số nguyên tố liên tiếp sau $p_i$. $n$ sẽ giảm, làm $S(n)$ giảm, nhưng $P(n)$ không giảm. Chung cuộc $A(n)$ giảm.

Vậy thì ta có thể thu hẹp phạm vi tìm kiếm hơn: $n=p_1p_2...p_k$ trong đó $p_i$ là số nguyên tố thứ $i$ ($p_1=2, p_2=3, ...$)

 

Thực ra có một trường hợp hợp số chúng ta chưa xét đến là $n=p^m$ nhưng trường hợp dễ xử lý vì $P(n)=1$.

 

Ta tính được $A(6)=S(6)-P(6)=3-2=1$. Vì thế $0 \le \min A(n) \le 1$. Câu hỏi đặt ra bây giờ là có $n$ để $A(n)=0$.

 

Thế nhưng $A(n)=0$ là vô lý. Thật vậy, giả sử tồn tại $n_0$ hợp số để $A(n_0)=0$ thì $S(n_0)=P(n_0)$, tức là mọi số nguyên tố nhỏ hơn $n_0$ đều là ước nguyên tố của $n_0$.

Ta viết $n_0$ dưới dạng $p_1p_2...p_k$ trong đó $p_i$ là số nguyên tố thứ $i$.

TH1: $k \ge 2$. Ta sẽ chứng minh tồn tại một số nguyên tố $p^*$ sao cho $p_k < p^* < n$.

Theo định lý Bertrand-Chebysev, luôn luôn tồn tại một số nguyên tố $p^*$ nằm giữa $p_k$ và $2p_k$ (chính là $p_{k+1}$), và $p^*$ hiển nhiên nhỏ hơn $n_0$ vì $p_1=2$ và $n_0 = p_1...p_k$.

Điều này cho thấy $S(n_0) > k$: vô lý với giả sử ban đầu.

TH2: $k = 1$. Tức là $n_0 = p^m$, và $n_0$ chỉ có duy nhất 1 số nguyên tố nhỏ hơn $n_0$. Nói cách khác $n_0 = 3$: vô lý vì $3$ là số nguyên tố.

 

 

Kết luận $A(n) = S(n) - P(n) \ge 1 \forall n$. Một ví dụ của dấu bằng là 6.

 

===========

Định lý Bertrand-Chebyserv: Luôn tồn tại một số nguyên tố giữa $n$ và $2n$.

https://en.wikipedia...and's_postulate


Luôn yêu để sống, luôn sống để học toán, luôn học toán để yêu!!! :D
$$\text{LOVE}\left( x \right)|_{x = \alpha}^\Omega = + \infty $$
I'm still there everywhere.

#4
Lemonjuice

Lemonjuice

    Trung sĩ

  • Thành viên
  • 118 Bài viết

Nối tiếp ý tưởng giữ nguyên $P(n)$ và hạ $S(n)$ thì có thể thấy nếu trong phân tích nguyên tố $p_1p_2...p_k$ của $n$ (giả sử $p_i$ tăng dần), nếu có $p_i$ và $p_{i+1}$ không phải hai số nguyên tố liên tiếp thì có thể thay $p_{i+1}$ bằng số nguyên tố liên tiếp sau $p_i$. $n$ sẽ giảm, làm $S(n)$ giảm, nhưng $P(n)$ không giảm. Chung cuộc $A(n)$ giảm.

Vậy thì ta có thể thu hẹp phạm vi tìm kiếm hơn: $n=p_1p_2...p_k$ trong đó $p_i$ là số nguyên tố thứ $i$ ($p_1=2, p_2=3, ...$)

 

Thực ra có một trường hợp hợp số chúng ta chưa xét đến là $n=p^m$ nhưng trường hợp dễ xử lý vì $P(n)=1$.

 

Ta tính được $A(6)=S(6)-P(6)=3-2=1$. Vì thế $0 \le \min A(n) \le 1$. Câu hỏi đặt ra bây giờ là có $n$ để $A(n)=0$.

 

Thế nhưng $A(n)=0$ là vô lý. Thật vậy, giả sử tồn tại $n_0$ hợp số để $A(n_0)=0$ thì $S(n_0)=P(n_0)$, tức là mọi số nguyên tố nhỏ hơn $n_0$ đều là ước nguyên tố của $n_0$.

Ta viết $n_0$ dưới dạng $p_1p_2...p_k$ trong đó $p_i$ là số nguyên tố thứ $i$.

TH1: $k \ge 2$. Ta sẽ chứng minh tồn tại một số nguyên tố $p^*$ sao cho $p_k < p^* < n$.

Theo định lý Bertrand-Chebysev, luôn luôn tồn tại một số nguyên tố $p^*$ nằm giữa $p_k$ và $2p_k$ (chính là $p_{k+1}$), và $p^*$ hiển nhiên nhỏ hơn $n_0$ vì $p_1=2$ và $n_0 = p_1...p_k$.

Điều này cho thấy $S(n_0) > k$: vô lý với giả sử ban đầu.

TH2: $k = 1$. Tức là $n_0 = p^m$, và $n_0$ chỉ có duy nhất 1 số nguyên tố nhỏ hơn $n_0$. Nói cách khác $n_0 = 3$: vô lý vì $3$ là số nguyên tố.

 

 

Kết luận $A(n) = S(n) - P(n) \ge 1 \forall n$. Một ví dụ của dấu bằng là 6.

 

===========

Định lý Bertrand-Chebyserv: Luôn tồn tại một số nguyên tố giữa $n$ và $2n$.

https://en.wikipedia...and's_postulate

Cảm ơn anh; em rất mong anh có thể tìm ra điều kiện của n để A(n) đạt GTNN. Đồng thời em cũng xin chứng minh chặt chẽ hơn phần bôi đỏ ở trên: Để A(n)đạt GTNN thì n phải là tích của k số nguyên tố đầu tiên. Dựa theo ý tưởng của anh ở trên thì ta bắt buộc phải có n là tích của các số nguyên tố liên tiếp nếu không sẽ dẫn đến S(n) tăng trong khi P(n) không thay đổi

Ta phân tích n thành $n=p_{1}p_{2}...p_{k}$ ; ta xét với n có một ước nguyên tố $p_{i}$ lớn hơn 5 ( trường hợp không có ước nguyên tố lớn hơn 5 thì ta dễ dàng kiểm tra) thì dẫn đến $n\geq 2^{k-1}p_{i}$

Dùng một kết quả khác của định lý Betrand: với n là số nguyên dương lớn hơn 5 thì giữa n và 2n luôn có ít nhất 2 số nguyên tố; suy ra có ít nhất $2^{k-1}+2$ (tính luôn cả số 3 và 2)  số nguyên tố không vượt quá $2^{k-1}p_{i}$ dẫn đến  có ít nhất $2^{k-1}$ số nguyên tố không vượt quá $n$ suy ra $A(n)=2^{k-1}-k+2$ lớn hơn 1 ( đoạn này đơn giản mà nhỉ) từ đây suy ra ĐPCM

Em nghĩ có thể dùng cách chứng minh này để tìm ra điều kiện của n để $A(n)$ đạt GTNN; mong anh perfectstrong cho ý kiến ạ.


Bài viết đã được chỉnh sửa nội dung bởi Lemonjuice: 22-05-2021 - 22:43


#5
perfectstrong

perfectstrong

    $LOVE(x)|_{x =\alpha}^\Omega=+\infty$

  • Quản lý Toán Ứng dụng
  • 4991 Bài viết

Cảm ơn anh; em rất mong anh có thể tìm ra điều kiện của n để A(n) đạt GTNN. Đồng thời em cũng xin chứng minh chặt chẽ hơn phần bôi đỏ ở trên: Để A(n)đạt GTNN thì n phải là tích của k số nguyên tố đầu tiên. Dựa theo ý tưởng của anh ở trên thì ta bắt buộc phải có n là tích của các số nguyên tố liên tiếp nếu không sẽ dẫn đến S(n) tăng trong khi P(n) không thay đổi

Ta phân tích n thành $n=p_{1}p_{2}...p_{k}$ ; ta xét với n có một ước nguyên tố $p_{i}$ lớn hơn 5 ( trường hợp không có ước nguyên tố lớn hơn 5 thì ta dễ dàng kiểm tra) thì dẫn đến $n\geq 2^{k-1}p_{i}$

Dùng một kết quả khác của định lý Betrand: với n là số nguyên dương lớn hơn 5 thì giữa n và 2n luôn có ít nhất 2 số nguyên tố; suy ra có ít nhất $2^{k-1}+2$ (tính luôn cả số 3 và 2)  số nguyên tố không vượt quá $2^{k-1}p_{i}$ dẫn đến  có ít nhất $2^{k-1}$ số nguyên tố không vượt quá $n$ suy ra $A(n)=2^{k-1}-k+2$ lớn hơn 1 ( đoạn này đơn giản mà nhỉ) từ đây suy ra ĐPCM

Em nghĩ có thể dùng cách chứng minh này để tìm ra điều kiện của n để $A(n)$ đạt GTNN; mong anh perfectstrong cho ý kiến ạ.

Điều kiện thì không anh không chắc.

Và ở trên anh chỉ tìm giá trị nhỏ nhất của $A(n)$ nên anh đưa ra một số phép biến đổi để có một phạm vi tìm kiếm dễ hơn, chứ anh không chứng minh chặt chẽ rằng GTNN chỉ nằm trong miền đấy. Nếu để ý thì $A(4)=1$ đấy em. Nên nhớ là $S(n)$ tăng không nghiêm ngặt. Nên giảm $n$ chưa chắc đã giảm ngặt $S(n)$.


Luôn yêu để sống, luôn sống để học toán, luôn học toán để yêu!!! :D
$$\text{LOVE}\left( x \right)|_{x = \alpha}^\Omega = + \infty $$
I'm still there everywhere.

#6
Lemonjuice

Lemonjuice

    Trung sĩ

  • Thành viên
  • 118 Bài viết

Cảm ơn anh; em rất mong anh có thể tìm ra điều kiện của n để A(n) đạt GTNN. Đồng thời em cũng xin chứng minh chặt chẽ hơn phần bôi đỏ ở trên: Để A(n)đạt GTNN thì n phải là tích của k số nguyên tố đầu tiên. Dựa theo ý tưởng của anh ở trên thì ta bắt buộc phải có n là tích của các số nguyên tố liên tiếp nếu không sẽ dẫn đến S(n) tăng trong khi P(n) không thay đổi

Ta phân tích n thành $n=p_{1}p_{2}...p_{k}$ ; ta xét với n có một ước nguyên tố $p_{i}$ lớn hơn 5 ( trường hợp không có ước nguyên tố lớn hơn 5 thì ta dễ dàng kiểm tra) thì dẫn đến $n\geq 2^{k-1}p_{i}$

Dùng một kết quả khác của định lý Betrand: với n là số nguyên dương lớn hơn 5 thì giữa n và 2n luôn có ít nhất 2 số nguyên tố; suy ra có ít nhất $2^{k-1}+2$ (tính luôn cả số 3 và 2)  số nguyên tố không vượt quá $2^{k-1}p_{i}$ dẫn đến  có ít nhất $2^{k-1}$ số nguyên tố không vượt quá $n$ suy ra $A(n)=2^{k-1}-k+2$ lớn hơn 1 ( đoạn này đơn giản mà nhỉ) từ đây suy ra ĐPCM

Em nghĩ có thể dùng cách chứng minh này để tìm ra điều kiện của n để $A(n)$ đạt GTNN; mong anh perfectstrong cho ý kiến ạ.

Hoàn thành nốt nào :)) (vừa nghĩ ra):

Dựa trên kết quả Để A(n)đạt GTNN thì n phải là tích của k số nguyên tố đầu tiên (**) thì ta xét nếu $n$ có nhiều hơn ba ước nguyên tố; sử dụng định lý định lý Betrand tương tự như bài trích trên (phần in đỏ) thì suy ra $A(n)=2^{k-1}-k+2$ lớn hơn 1

Vậy ta chỉ cần xét những số $n$ có không quá ba ước nguyên tố mà dựa kết quả (**) thì $n$ phải là tích của không quá ba số nguyên tố đầu tiên; từ đây ta có 6 là hợp số duy nhất thỏa điều kiện này

Còn với những số có dạng $p^{k}$ với $p$ là một số nguyên tố thì chỉ có $n=4$ là thỏa từ đây suy ra ĐPCM.

 

P/S: Bài toán này mà thay thành: Tìm số $n$ nguyên dương để $A(n)=S(n)-P(n)=d$ với  $d$ là một số nguyên dương cố định cho trước nào đó thì không biết làm được không nhỉ ( $d=3$ hoặc 2 chẳng hạn  :lol: ) không biết mọi người có ý kiến sao ( anh perfectstrong xơi nốt giùm em bài tổng quát nà được không ạ :D )



#7
perfectstrong

perfectstrong

    $LOVE(x)|_{x =\alpha}^\Omega=+\infty$

  • Quản lý Toán Ứng dụng
  • 4991 Bài viết

Nếu tổng quát hóa lên $A(n)=d$ thì khó vì như vầy là đang khảo sát $S(n)$, mà hàm này thì nổi tiếng rồi :D


Luôn yêu để sống, luôn sống để học toán, luôn học toán để yêu!!! :D
$$\text{LOVE}\left( x \right)|_{x = \alpha}^\Omega = + \infty $$
I'm still there everywhere.




3 người đang xem chủ đề

0 thành viên, 3 khách, 0 thành viên ẩn danh