It seems really random. 1d is 1353, 1L is 22, 11 is 256, 11L is 78508, 11x is 78508, 111 is 65536, 112 is is 1335, 113 is 1330, 114 is 1330, 1L1 is 1330. I thought it was 58 to the power of the number of digits. Why isn't it?
There are two parts to this.
First is leading 1s. A leading 1 represents a 0 byte i.e. 8 bits. This means that for every additional 1 you prefix your search string with the difficulty increases by 256 (2^8). You can see this easily by checking the difficulty of prefixes 1, 11, 111 etc.
Second is other characters. Here the difficulty changes depending on how many bits you are specifying, because as your value is converted from base58 to an integer value and from there to a power of 2. Depending on your second number in your 2-digit prefix the difficulty will move around a bit (plus there will be rounding errors). Again, easy to see with prefixes of 12 and 1z (which are 1 and 57 in base58 encoding, respectively).
Once you get past all of that you should find that your 58 to the power of the number of digits comes in to play. For example the difficulty of 1234 should be 58 times the difficulty of 123.