圖蘭篩法
在數論中,圖蘭篩法(Turán sieve)是一個用以估計滿足特定條件的「篩選過的」正整數集大小的技巧,而這些條件一般都以同餘表示。這篩法由圖蘭·帕爾於1934年發展。
描述
在篩法的術語中,圖蘭篩法是一種「組合篩法」,也就是一種透過小心應用容斥原理進行「篩選」的篩法。此種篩法可給出「篩選過的」的集合大小的上界。
設 為不大於 的正整數的集合,並假定 為質數的集合,然後設 是 中可為 中的質數 整除的數組成的集合;此外,可設 為 中的不同質數的乘積,在這種狀況下,可相應地定義 為 中可被 整除的數的集合,並定義 為 本身。
設 為任意實數,而 為 中不大於 的質數的乘積,那這篩法的目標就是估計下式:
我們可以假定說在 為質數 的狀況下, 可由下式估計:
而在 為相異質數 與 的乘積狀況下, 可由下式估計:
其中 是 的元素個數,而 則是一個使得 的函數。
設 ,可得下式:
應用
參考資料
- Alina Carmen Cojocaru; M. Ram Murty. An introduction to sieve methods and their applications. London Mathematical Society Student Texts 66. Cambridge University Press. : 47–62. ISBN 0-521-61275-6.
- Greaves, George. Sieves in number theory. Springer-Verlag. 2001. ISBN 3-540-41647-1.
- Halberstam, Heini; Richert, H.-E. Sieve Methods. London Mathematical Society Monographs 4. Academic Press. 1974. ISBN 0-12-318250-6. MR 0424730. Zbl 0298.10026.
- Christopher Hooley. Applications of sieve methods to the theory of numbers. Cambridge University Press. 1976: 21. ISBN 0-521-20915-3.