How does Base58Check prefix character prediction work? I'm trying to implement Base58Check as a learning exercise and I came across the different types of prefixes as summarised here.

I wonder however how to arrive in the expected prefix characters from the prefix Byte. 
Why the same byte can lead to different characters, and how those come to be.

My initial assumption was that the first character is the Base58 encode of the prefix byte, but that seems wrong, the address byte 0x00 maps to "1" because it's a leading zero, but the second example of P2SH with 0x05 should map to char "6" but instead it maps to "3". And the WIF prefix of 0x80 can map to either "5" (uncompressed), "K" or "L" (compressed) even though the prefix is the same.

Also on my tests that mapping only seems to work after I add the 4 byte checksum in the end of the array. If I encode the array without the checksum the result has different prefix characters.

So, how is the expected prefix characters of Base58Check derived from the prefix?
This is not unique to Base58 encoding (nor the Check part). It's about base conversion:

The number 13 in hex is 0x0d, the number 18 in hex is 0x12. Even though in decimal both start with 1, their first digits in hex are different. In fact, in Bitcoin's address format, unlike the example above, that would be comparing d with 1 instead of 0 with 1 because encoded Bitcoin addresses have different lengths.

What's common is the largest factor deciding the significant digits are the significant digits. That's why if you want to calculate a few first characters of Base58check instead of adding 4 byte checksum at the end you can add 4 empty bytes and the first characters of the result would be same. Most of the time, (unless a base is a power of another, such as base-2 and base-16. Also note that 1s in front of addresses in Bitcoin are specially handled) the length of the input should be the same to calculate the same first few characters.


  So, how is the expected prefix characters of Base58Check derived from the prefix?


We also need to have an input of constant length (including 4 bytes of Base58check). I assume we have the first few bytes of the input. We pad the rest with zeros and Base58 encode it. We than pad the rest with 1s (or 255s if bytes) and Base58 encode.

Then we open the Bae58 alphabet:

123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz


Suppose we calculated 1FGMQ... as the lower range and 1FJwz... as the higher range. As long as the input is of the same length, no matter what you fill in to the rest of the bytes the encoded address will be between those two.