Yesterday Dan Harkins cornered me in the hall and asked me
the following question:

Given a random 128-bit integerdand another random x-bit integernwhere x >> 128, what is the probability thatnis an even multiple ofd.

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..2^{128}-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 10
^{43}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 10^{43}isn't that far off 2^{128}, 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.

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

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)

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?