August 13, 2010

Distribution of Factor Count for Numbers

I extracted the frequency of the factors for numbers in the range [2,  10^6]. It was quiet interesting for me. Why is it that 2,688 numbers have 30 unique factors but there are ZERO numbers that have 32 factors?

While studying about randomized algorithms in wikipedia, one of the very first algorithms in this context is the Miller-Rabin primality test and an important statement in their algorithm is that:

"If n is composite then at least three-fourths of the natural numbers less than n are witnesses to its compositeness."[1,2]

But a number like 22 has only two numbers are witnesses of its compositeness (2 and 11). So what does that mean. I thought that it could be true for most numbers if we get to infinity, therefore I counted the number of factors (witness of compisiteness) of the numbers from two to one million. And as the mubers grow their factor count become less comparable to their magnitude. So what does that quote mean?

[1] .
[2]. Dietzfelbinger, M. and Hagerup, T. and Katajainen, J. and Penttonen, M. "A Reliable Randomized Algorithm for the Closest-Pair Problem", Journal of Algorithms, Vol 25, Issue 1, 1997.

No comments:

Post a Comment