梁增勇
摘 要:
在研究質(zhì)數(shù)的問(wèn)題中常常運(yùn)用到篩法計(jì)算質(zhì)數(shù)的個(gè)數(shù)。本文介紹用更苛刻的篩除法求出質(zhì)數(shù)對(duì)的可靠下限,同時(shí)用函數(shù)等數(shù)學(xué)分析的方法進(jìn)行分析,即可解決這類性質(zhì)的關(guān)鍵問(wèn)題。
關(guān)鍵詞:集合;函數(shù);篩法;整數(shù)對(duì);數(shù)學(xué)分析
一、本文使用的數(shù)學(xué)符號(hào)的定義:
全體非負(fù)整數(shù)的集合通常簡(jiǎn)稱非負(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ù)對(duì)個(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ì)算。對(duì)于更大范圍的數(shù)據(jù)運(yùn)算是無(wú)能為力的。下面我們介紹運(yùn)用篩法、函數(shù)和數(shù)學(xué)分析解決這類性質(zhì)的問(wèn)題的幾個(gè)對(duì)策和方法。
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ì)的對(duì)偶數(shù)對(duì),并篩除所有含合數(shù)的對(duì)偶數(shù)對(duì)。根據(jù)定理2,僅篩除上行含合數(shù)的對(duì)偶數(shù)對(duì),余下個(gè)數(shù)為 card(B\-\{2,3,…,P\-\{i+1\}\} )≥ф′(n)= n (1-13)…(1-1P\-i)
再考慮對(duì)帶奇合數(shù)對(duì)偶數(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ì)元素對(duì)偶數(shù)對(duì)個(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)
成立,必定有一對(duì)或一對(duì)以上的同性質(zhì)(例如相關(guān)質(zhì)數(shù))對(duì)偶數(shù)對(duì)存在。
證 已知N′的元素排列成n組同性質(zhì)對(duì)偶數(shù)。由定理3可知,集合D已經(jīng)不含任何的合數(shù),d(n)為集合D元素個(gè)數(shù)的下限函數(shù)。 那么,當(dāng)d(n) ≥ 4 ( 取保守一點(diǎn)) ),可組成至少兩對(duì)對(duì)偶數(shù)(可能有一對(duì)含數(shù)1)這樣,至少 有一對(duì)或一對(duì)以上對(duì)偶數(shù)對(duì)全是同性質(zhì)整數(shù)存在。
定理5 令N′為N之子集 ,card(N′)=2n ,2n≤p\-m\+2+1, 則
(5)
證 對(duì)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