How many vanity adresses per prefix are there ?

[bhafner]

Hi everyone,

I was wondering how many different vanity adresses that begin with the same series of letters or figures there are.

Given that the bitcoin adresses exist in a limited (while astronomical) quantity, and that there is a kind of validation system (you cannot just change a letter in a BTC adress), there must be a way to calculate this, with the relationship to the lenght of the vanity combination.

Can someone help ?

[cassini]

Let's start with the RIPEMD-160 hash in the center of this image:
https://en.bitcoin.it/wiki/File:PubKeyToAddr.png
So we have 160 bits or 20 bytes.
Which is 2^160 possible combinations.
Now we add the "1" to the front and 4 bytes checksum (that's why not every combination is valid),
which gives us 25 bytes. According to
http://en.wikipedia.org/wiki/Base64
(where we assume that Bitcoin's Base58 leads to roughly the same numbers of characters as Base64 does)
we get four thirds of 25 bytes, which equals to something between 33 and 34 bytes. This is our Bitcoin address.
Hence our two little equations are:
- We have 2^( n*8 ) valid combinations.
- We get (n+5)/3*4 characters for the Bitcoin address.
Replace n with 20 for the unrestricted Bitcoin address space.

Now you want to take e.g. 6 characters out of the equation, because you choose a vanity address like this one:
1aaaaaaX298sdf3kjh394jh499o38te36a
So we have not 33 but 27 variable characters:

(n+5)/3*4 = 27,
and n=15 approximately.

Result: You end up with 2^( 15*8 ) valid combinations instead of 2^(20*8) of the full Bitcoin address space.

So the rough approximation is:
2^(( (33-x)/4*3 - 5 ) * 8 )
where x is the number of vanity characters (6 in the example above).