# Solve for n: 1 - e^((-k (k - 1))/(2 n)) - z = 0?

With the knowledge that the probability of a hash collision is (see: Hash Collision Probabilities):

1 - e^((-k * (k - 1)) / (2 * n))

Where k is the number of input values and n is the number of possible hash values. I want to find the solution for n, given the probability of collisions is z:

1 - e^((-k * (k - 1)) / (2 * n)) - z = 0

Utilizing Mathematica, I entered:

Reduce[1 - e^((-k*(k-1))/(2*n)) - z == 0, n]


Output:

C[1] \[Element] Integers
&& -1 + z != 0
&& ((n != 0 && (k == 0 || k == 1) && z == 0)
|| (2 I \[Pi] C[1] + Log[1/(1 - z)] != 0 && (-1 + k) k != 0
&& n == ((-1 + k) k)/(2 (2 I \[Pi] C[1] + Log[1/(1 - z)]))))


Now, I'm not sure what value to use for C[1] and the meaning of 'I'. I need to translate the equation into C code.

## 2 Answers

I wonder if $e$ should not be $E$. In any manner, if you type

    Solve[1 - E^((-k*(k-1))/(2*n)) - z == 0, n]


you should get $$n=-\frac{(k-1) k}{2 \log (1-z)}$$ which is a real number. Round it the way you want.

• I must be entering 'E' incorrectly as it always results in a complex number for me. How do I enter 'E' in mathematica? – Coder Oct 17 '15 at 4:20
• I even tried: Solve[1 - Exp[(-k * (k - 1)) / (2*n)] - z == 0, n] and get: {{n -> ConditionalExpression[((-1 + k) k)/( 2 (2 I [Pi] C[1] + Log[1/(1 - z)])), C[1] [Element] Integers]}} – Coder Oct 17 '15 at 4:27
• I cannot tell you more since I do not have Mathematica (even if I know a little). Did you put somewhere restrictions on $k,n,z$ prior to the Solve command ? I suggest you close your session and just type the command. Please, let me know. – Claude Leibovici Oct 17 '15 at 4:37

If I instead use Solve and limit the domain to Reals:

Solve[1-Exp[-k(k-1)/(2n)]-z==0, n, Reals]


I get:

$$n = \frac{-k + k^2}{2log(\frac{1}{1 - z})}$$

Where (0 < k < 1 && 0 < z < 1) || (0 < k < 1 && z < 0) || (k > 1 && 0 < z < 1) || (k > 1 && z < 0) || (k < 0 && 0 < z < 1) || (k < 0 && z < 0)