# What is the smallest alphanumeric string that has 10 million permutations?

I'm aiming to create UUIDs, for a project I'm working on.

The standard UUID generators create a very long strings. I'm only anticipating a maximum of 10 million uses and because I'm storing that many potential uuids and other information in-memory, I want to cut it down a bit.

What is the shortest string length containing a-z, A-Z and 0-9 that is good for 10 million unique uuids? If I shorten the string like this, will I also increase the chance of repeats or are the chances of repeats still fairly astronomical?

• Since there are $62$ allowed characters, there will be $62^L$ strings of length $L$. Thus you are looking for $L$ such that $62^L = 10^7$ or equivalently $L = \log_{62}(10^7) \approx 3.9$. Thus the ideal string length would be $4$ characters. – Abel Jun 13 '13 at 8:50
• permutation doesn't mean what you might think it means. A permutation is a rearrangement of some objects, like for example the characters in a string. In general, $n$ distinguishable objects can be arranged in $n!$ ways. However, a string over some alphabet isn't in general a permutation of the alphabet, since it may include some letters more than once and others not at all. – fgp Jun 13 '13 at 9:00

From the table in this article, you can see that if you have about six million 64-bit UUIDs, then the probability of there being a collision is about $10^{-6}$, which I'd expect might be the correct order of magnitude to avoid all problems.
Given a 62-character alphabet, a 64-bit UUID requires eleven characters since $$\frac{\log2^{64}}{\log62}\;\approx\;10.75.$$ The article also gives a simple approximation which can be rearranged to give the formula $m=n^2/2p$ for the required number of UUIDs, where $n$ is the maximum number of users ($10^7$ for you) and $p$ is the acceptable chance of a collision.
So, for example, if you're happy with a $10^{-3}$ (0.1%) chance of failure, then you need approximately $5\times10^{16}$ UUIDs which still requires ten characters.