篩法在實(shí)際應(yīng)用的探討?yīng)?/h1>
2018-01-09 07:30:05梁增勇
山東青年 2017年8期
梁增勇
摘 要：
在研究質(zhì)數(shù)的問題中常常運(yùn)用到篩法計(jì)算質(zhì)數(shù)的個(gè)數(shù)。本文介紹用更苛刻的篩除法求出質(zhì)數(shù)對的可靠下限，同時(shí)用函數(shù)等數(shù)學(xué)分析的方法進(jìn)行分析，即可解決這類性質(zhì)的關(guān)鍵問題。
關(guān)鍵詞：集合；函數(shù)；篩法；整數(shù)對；數(shù)學(xué)分析
一、本文使用的數(shù)學(xué)符號的定義：
全體非負(fù)整數(shù)的集合通常簡稱非負(fù)整數(shù)集（或自然數(shù)集），記作N[1]。本文中
A表示[1，n]區(qū)間正整數(shù)的集合，即A ={1，2，3，…，n}， 集合A的元素個(gè)數(shù)記為card （A）；
A＼-p為含有p素因子倍數(shù)的子集， 即A＼-p ={1p，2p，3p， 4p， 5p，……}， A＼-＼{2，3＼}={2，3，4，6，8，9}，（n=10） ；
B＼-p 為集合A不含p素因子合數(shù)子集（除了2），例如B＼-2是奇數(shù)的子集， B＼-＼{2，3＼}={1，3，5，7}，（n=10）；
P表示素?cái)?shù)的集合，p或p＼-m 表示素?cái)?shù)，即P={2，3，5，7，11，13，……， p， ……，} 或 P = {p＼-1 ， p＼-2 ， p＼-3 ，…， p＼-m ，…}，
ф（n）為歐拉函數(shù)，ф′（n）、h（n）為非合數(shù)個(gè)數(shù)的下限函數(shù)。d（n）為質(zhì)數(shù)對個(gè)數(shù)的下限函數(shù)。
容斥原理是在組合數(shù)學(xué)中應(yīng)用頗為廣泛的一個(gè)工具，它常使用到容斥公式[2]。例如：
例1 設(shè)A是一個(gè)由整數(shù)組成的有限集合，d＼-1， d＼-2， …， d＼-m 是給定的正整數(shù)，再設(shè)A＼-d 表A中被正整數(shù)d整除的元素組成的子集，那么，A中不能被任一dj（1≤j≤m）整除的元素的個(gè)數(shù)等于
|A | -Σ1≤i≤m|Ad＼-i| + Σ1≤i≤j≤m|Ad＼-j∩ Ad＼-j |-… + （-1）＼+＼{m-1＼} | Ad＼-1∩ Ad＼-2∩…∩Ad＼-m|
由于取整運(yùn)算十分是復(fù)雜， 僅可以在小范圍內(nèi)計(jì)算。對于更大范圍的數(shù)據(jù)運(yùn)算是無能為力的。下面我們介紹運(yùn)用篩法、函數(shù)和數(shù)學(xué)分析解決這類性質(zhì)的問題的幾個(gè)對策和方法。
1、質(zhì)數(shù)個(gè)數(shù)的下限函數(shù)
引理1[2]. 若p為任一質(zhì)數(shù)，A＼-p 為n個(gè)連續(xù)自然數(shù)中含質(zhì)數(shù)p的所有倍數(shù)的集合，則
card（A＼-p）≤np]= [kn+rp]=k ≤np = k+rp，因?yàn)?（rp ≥0） ， 所以 card（A＼-p）≤np 。
定理1. 若p為任一質(zhì)數(shù)，B＼-p 為n個(gè)連續(xù)自然數(shù)篩除去質(zhì)數(shù)p的所有合數(shù)的集合，則
Card（B＼-p）≥n（1-1p ）。
證 由引理1得，card（A＼-p） ≤np ，則card（B＼-p）=n-card（A＼-p）≥n-np = n（1-1p
）。
引理2 （Euler函數(shù)）[3] 若 n含任意質(zhì)數(shù)p＼-i、p＼-j、……p＼-k 之因子，則 ф（n）= n （1-np＼-i ） （1-np＼-j）…（1-np＼-k） （1）
定理2. 若2，3，…，p＼-i為質(zhì)數(shù)，p＼-i≤（2）
證 由引理2 可知， 函數(shù)φ（n） 是當(dāng)n為2×3×5×……×p＼-k 時(shí)可計(jì)算得之準(zhǔn)確值，當(dāng)n與上述整數(shù)有互素的情況，因函數(shù)ф（n）轉(zhuǎn)為ф′（n） ，由定理1可知每個(gè)因子（1-n22P＼-1 ） （ 1-2P＼-22P＼-i ）（3）
證 集合H的2n自然數(shù)可排成上、下兩行組成n個(gè)相同性質(zhì)的對偶數(shù)對，并篩除所有含合數(shù)的對偶數(shù)對。根據(jù)定理2，僅篩除上行含合數(shù)的對偶數(shù)對，余下個(gè)數(shù)為 card（B＼-＼{2，3，…，P＼-＼{i+1＼}＼} ）≥ф′（n）= n （1-13）…（1-1P＼-i）
再考慮對帶奇合數(shù)對偶數(shù)重復(fù)篩除一次，即將括弧中1/p＼-i改為2/p＼-i，得到
card（B＼-＼{2，3，…，P＼-＼{i+1＼}＼}）≥d（n）= n（1-23）…（1-2P＼-i）
此即所謂重復(fù)篩除法，函數(shù)d（n）必然小于或等于非合性質(zhì)元素對偶數(shù)對個(gè)數(shù)的實(shí)際值card（D）， 即
card（D） ≥d（n） = n2（ 1-2P＼-2） （ 1-2P＼-2 ）…（ 1-2P＼-i）
定理4 令N′為N之子集 ，card（N′）=2n ，2n≤p＼-m＼+2+1， 那么當(dāng)
n2Πmi=2（1-2P＼-i）≥4（4）
成立，必定有一對或一對以上的同性質(zhì)（例如相關(guān)質(zhì)數(shù)）對偶數(shù)對存在。
證 已知N′的元素排列成n組同性質(zhì)對偶數(shù)。由定理3可知，集合D已經(jīng)不含任何的合數(shù)，d（n）為集合D元素個(gè)數(shù)的下限函數(shù)。 那么，當(dāng)d（n） ≥ 4 （ 取保守一點(diǎn)） ），可組成至少兩對對偶數(shù)（可能有一對含數(shù)1）這樣，至少 有一對或一對以上對偶數(shù)對全是同性質(zhì)整數(shù)存在。
定理5 令N′為N之子集 ，card（N′）=2n ，2n≤p＼-m＼+2+1， 則
（5）
證 對m使用數(shù)學(xué)歸納法[2]：1）當(dāng) m=6， n=170，d（n′）= [參考文獻(xiàn)]
[1] 同濟(jì)大學(xué)應(yīng)用數(shù)學(xué)系主編 . 高等數(shù)學(xué).[M]高等教育出版社，1978 ：1-23.
[2]潘承洞，潘承彪. 初等數(shù)論. [M]北京大學(xué)出版社， 2003：71-76.
[3]G.H.Hardy，E.M.Wright，An Introduction to the Theory of Numbers.[M].人民郵電出版社， 2007：52-53.
（作者單位：廣西婦幼保健院，廣西 南寧 530000）endprint
梁增勇
摘 要：
在研究質(zhì)數(shù)的問題中常常運(yùn)用到篩法計(jì)算質(zhì)數(shù)的個(gè)數(shù)。本文介紹用更苛刻的篩除法求出質(zhì)數(shù)對的可靠下限，同時(shí)用函數(shù)等數(shù)學(xué)分析的方法進(jìn)行分析，即可解決這類性質(zhì)的關(guān)鍵問題。
關(guān)鍵詞：集合；函數(shù)；篩法；整數(shù)對；數(shù)學(xué)分析
一、本文使用的數(shù)學(xué)符號的定義：
全體非負(fù)整數(shù)的集合通常簡稱非負(fù)整數(shù)集（或自然數(shù)集），記作N[1]。本文中
A表示[1，n]區(qū)間正整數(shù)的集合，即A ={1，2，3，…，n}， 集合A的元素個(gè)數(shù)記為card （A）；
A＼-p為含有p素因子倍數(shù)的子集， 即A＼-p ={1p，2p，3p， 4p， 5p，……}， A＼-＼{2，3＼}={2，3，4，6，8，9}，（n=10） ；
B＼-p 為集合A不含p素因子合數(shù)子集（除了2），例如B＼-2是奇數(shù)的子集， B＼-＼{2，3＼}={1，3，5，7}，（n=10）；
P表示素?cái)?shù)的集合，p或p＼-m 表示素?cái)?shù)，即P={2，3，5，7，11，13，……， p， ……，} 或 P = {p＼-1 ， p＼-2 ， p＼-3 ，…， p＼-m ，…}，
ф（n）為歐拉函數(shù)，ф′（n）、h（n）為非合數(shù)個(gè)數(shù)的下限函數(shù)。d（n）為質(zhì)數(shù)對個(gè)數(shù)的下限函數(shù)。
容斥原理是在組合數(shù)學(xué)中應(yīng)用頗為廣泛的一個(gè)工具，它常使用到容斥公式[2]。例如：
例1 設(shè)A是一個(gè)由整數(shù)組成的有限集合，d＼-1， d＼-2， …， d＼-m 是給定的正整數(shù)，再設(shè)A＼-d 表A中被正整數(shù)d整除的元素組成的子集，那么，A中不能被任一dj（1≤j≤m）整除的元素的個(gè)數(shù)等于
|A | -Σ1≤i≤m|Ad＼-i| + Σ1≤i≤j≤m|Ad＼-j∩ Ad＼-j |-… + （-1）＼+＼{m-1＼} | Ad＼-1∩ Ad＼-2∩…∩Ad＼-m|
由于取整運(yùn)算十分是復(fù)雜， 僅可以在小范圍內(nèi)計(jì)算。對于更大范圍的數(shù)據(jù)運(yùn)算是無能為力的。下面我們介紹運(yùn)用篩法、函數(shù)和數(shù)學(xué)分析解決這類性質(zhì)的問題的幾個(gè)對策和方法。
1、質(zhì)數(shù)個(gè)數(shù)的下限函數(shù)
引理1[2]. 若p為任一質(zhì)數(shù)，A＼-p 為n個(gè)連續(xù)自然數(shù)中含質(zhì)數(shù)p的所有倍數(shù)的集合，則
card（A＼-p）≤np]= [kn+rp]=k ≤np = k+rp，因?yàn)?（rp ≥0） ， 所以 card（A＼-p）≤np 。
定理1. 若p為任一質(zhì)數(shù)，B＼-p 為n個(gè)連續(xù)自然數(shù)篩除去質(zhì)數(shù)p的所有合數(shù)的集合，則
Card（B＼-p）≥n（1-1p ）。
證 由引理1得，card（A＼-p） ≤np ，則card（B＼-p）=n-card（A＼-p）≥n-np = n（1-1p
）。
引理2 （Euler函數(shù)）[3] 若 n含任意質(zhì)數(shù)p＼-i、p＼-j、……p＼-k 之因子，則 ф（n）= n （1-np＼-i ） （1-np＼-j）…（1-np＼-k） （1）
定理2. 若2，3，…，p＼-i為質(zhì)數(shù)，p＼-i≤（2）
證 由引理2 可知， 函數(shù)φ（n） 是當(dāng)n為2×3×5×……×p＼-k 時(shí)可計(jì)算得之準(zhǔn)確值，當(dāng)n與上述整數(shù)有互素的情況，因函數(shù)ф（n）轉(zhuǎn)為ф′（n） ，由定理1可知每個(gè)因子（1-n22P＼-1 ） （ 1-2P＼-22P＼-i ）（3）
證 集合H的2n自然數(shù)可排成上、下兩行組成n個(gè)相同性質(zhì)的對偶數(shù)對，并篩除所有含合數(shù)的對偶數(shù)對。根據(jù)定理2，僅篩除上行含合數(shù)的對偶數(shù)對，余下個(gè)數(shù)為 card（B＼-＼{2，3，…，P＼-＼{i+1＼}＼} ）≥ф′（n）= n （1-13）…（1-1P＼-i）
再考慮對帶奇合數(shù)對偶數(shù)重復(fù)篩除一次，即將括弧中1/p＼-i改為2/p＼-i，得到
card（B＼-＼{2，3，…，P＼-＼{i+1＼}＼}）≥d（n）= n（1-23）…（1-2P＼-i）
此即所謂重復(fù)篩除法，函數(shù)d（n）必然小于或等于非合性質(zhì)元素對偶數(shù)對個(gè)數(shù)的實(shí)際值card（D）， 即
card（D） ≥d（n） = n2（ 1-2P＼-2） （ 1-2P＼-2 ）…（ 1-2P＼-i）
定理4 令N′為N之子集 ，card（N′）=2n ，2n≤p＼-m＼+2+1， 那么當(dāng)
n2Πmi=2（1-2P＼-i）≥4（4）
成立，必定有一對或一對以上的同性質(zhì)（例如相關(guān)質(zhì)數(shù)）對偶數(shù)對存在。
證 已知N′的元素排列成n組同性質(zhì)對偶數(shù)。由定理3可知，集合D已經(jīng)不含任何的合數(shù)，d（n）為集合D元素個(gè)數(shù)的下限函數(shù)。 那么，當(dāng)d（n） ≥ 4 （ 取保守一點(diǎn)） ），可組成至少兩對對偶數(shù)（可能有一對含數(shù)1）這樣，至少 有一對或一對以上對偶數(shù)對全是同性質(zhì)整數(shù)存在。
定理5 令N′為N之子集 ，card（N′）=2n ，2n≤p＼-m＼+2+1， 則
（5）
證 對m使用數(shù)學(xué)歸納法[2]：1）當(dāng) m=6， n=170，d（n′）= [參考文獻(xiàn)]
[1] 同濟(jì)大學(xué)應(yīng)用數(shù)學(xué)系主編 . 高等數(shù)學(xué).[M]高等教育出版社，1978 ：1-23.
[2]潘承洞，潘承彪. 初等數(shù)論. [M]北京大學(xué)出版社， 2003：71-76.
[3]G.H.Hardy，E.M.Wright，An Introduction to the Theory of Numbers.[M].人民郵電出版社， 2007：52-53.
（作者單位：廣西婦幼保健院，廣西 南寧 530000）endprint
