A note on the distribution of the number of prime factors of the integers

TitleA note on the distribution of the number of prime factors of the integers
Publication TypeJournal Articles
Year of Publication2008
AuthorsSrinivasan A
JournalInformation Processing Letters
Volume109
Issue2
Pagination133 - 135
Date Published2008/12/31/
ISBN Number0020-0190
KeywordsChernoff bounds, Dependent random variables, Primes, Probabilistic number theory, randomized algorithms, Tail bounds
Abstract

The Chernoff–Hoeffding bounds are fundamental probabilistic tools. An elementary approach is presented to obtain a Chernoff-type upper-tail bound for the number of prime factors of a random integer in { 1 , 2 , … , n } . The method illustrates tail bounds in negatively-correlated settings.

URLhttp://www.sciencedirect.com/science/article/pii/S0020019008002688
DOI10.1016/j.ipl.2008.09.010