Base58( 0x12 | S0 | V0 | checksum ) = “ 4 ..........” [95 chars]
Base58( 0x2A | Si | Vi | checksum ) = “ 8 ..........” [95 chars]
Base58( 0x13 | S0 | V0 | payID | checksum ) = “ 4 ..........” [106 chars]
source (disclaimer: mine): https://www.getmonero.org/library/MoneroAddressesCheatsheet20201206.pdf
I guess the problem you are having w/ Base58 comes from the tools you are using not applying Base58 to strings as Monero does.
From https://xmr.llcoins.net/addresstests.html :
[...] 4. As a last step, this 69-byte string is converted to Base58. However, it's not done all at once like a Bitcoin address, but rather in 8-byte blocks. This gives us eight full-sized blocks and one 5-byte block. Eight bytes converts to 11 or less Base58 characters; if a particular block converts to <11 characters, the conversion pads it with "1"s (1 is 0 in Base58). Likewise, the final 5-byte block can convert to 7 or less Base58 digits; the conversion will ensure the result is 7 digits. Due to the conditional padding, the 69-byte string will always convert to 95 Base58 characters (8 * 11 + 7). [...]