国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

篩法在實(shí)際應(yīng)用的探討?yīng)?/h1>
2018-01-09 07:30梁增勇
山東青年 2017年8期
關(guān)鍵詞:集合數(shù)學(xué)分析函數(shù)

梁增勇

摘 要:

在研究質(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

猜你喜歡
集合數(shù)學(xué)分析函數(shù)
二次函數(shù)
二次函數(shù)
函數(shù)備考精講
一道數(shù)學(xué)填空題引發(fā)對(duì)細(xì)節(jié)的思考
解讀《集合》
學(xué)習(xí)《數(shù)學(xué)分析》的讀書報(bào)告

抚顺市| 连城县| 额敏县| 北票市| 白城市| 泰来县| 囊谦县| 册亨县| 合川市| 鹤岗市| 南丹县| 沛县| 茶陵县| 乌鲁木齐县| 漯河市| 延安市| 岐山县| 西乡县| 静宁县| 伊金霍洛旗| 七台河市| 东台市| 宣化县| 杭锦旗| 故城县| 沿河| 武隆县| 苍南县| 富川| 洛宁县| 依安县| 岳阳市| 富裕县| 玛多县| 确山县| 石河子市| 拉萨市| 绥棱县| 平潭县| 化州市| 焉耆|