« FIPS certification pays off | Main | Forget net neutrality, how about hard drive neutrality? »
December 4, 2007
The probability of divisibility
Yesterday Dan Harkins cornered me in the hall and asked me the following question:Given a random 128-bit integer d and another random x-bit integer n where x >> 128, what is the probability that n is an even multiple of d.
My immediate answer was 2-128. My second was to retract this and suggest that Dan ask a mathematician. My third was to try to work the problem. My reasoning below.
- The probability that a random number is divisible by 1 is 1, divisible by 2 is 1/2, divisible by 3 is 1/3, etc.
- If we assume that d is randomly distributed over
1..2128-1, then each of these probabilities is
equiprobably, so we can compute:
- This series (1 + 1/2 + 1/3, ...), the harmonic series.
- The Harmonic series diverges, but very slowly. As the Wikipedia page says, the first 1043 terms sum to less than 100.
- Since we're interested in the mean probability, we divide the sum by the number of terms, d, and since 1043 isn't that far off 2128, this means that we're looking at something like 2-120.
Unless I've screwed something up (always possible), I guess my intuition isn't completely broken.
UPDATE: 2/3 -> 1/3. Thanks to Dan for the fix.
Posted by ekr at December 4, 2007 5:04 PM | Filed under: Misc
Comments
I believe you're right. I think the probablity is log(x)/x with the log base e and x is the amount of numbers
Posted by: E at December 4, 2007 6:11 PM
Yup. The harmonic series from 1 to n has a lower bound of ln(n)+1/n and an upper bound of ln(n)+1.
To see this, consider the integral of f(x)=1/x and compare the area under the curve to that obtained by creating a bunch of rectangles of width 1 and height = the left end-point y-value (for the upper bound) and the right end-point y-value (for the lower bound)
Posted by: Prasanna at December 4, 2007 10:08 PM
Isn't the probability 1/d?
Makes one wonder about the source of the question.
Would there be a probability that d would be 1?
Is the range assumtion valid?
Are we interested in the mean probability, or a friendlier probability?
Posted by: Jim Lebeau at December 5, 2007 8:05 AM