It's triple zero, used to call the emergency services in Australia. That is the lowest possible number. We did it!
Well that was boring. And you, dear reader, probably don't even live in Australia,* so it's not your shortest phone number. Let's come up with a new rule to make this more interesting: Everyone should be able to call the number.
That means we'll only consider numbers that can start with an international country calling code. (Count the country code as part of the full number.) We'll have to ignore short codes, the emergency services, carrier-specific codes, and Arogyavani.
The rule means the number must exist — it has to be registered to someone or something. But I'm not going to call up random people/organisations to verify things, so we'll just say that if the number's been written on the internet by a reputable source, it counts.
Spoilers below
Maybe try the game yourself and see how well you can do!
Strategy
The most important way to make numbers smaller is to remove as many digits as you can. Phone numbers are made up of the international country calling code followed by the local code. Both of those parts can differ in length depending on the country. In general, the local codes of smaller countries have fewer digits - but since smaller countries are less relevant, they were assigned longer international codes. So there's a trade-off there.
Shorter international codes
The only single-digit international code is +1 for the United States of America and Canada, but all their phone numbers seem to be in the format (XXX) XXX-XXXX. That's a total of 11 digits, which is waaaay too long.
Let's try focusing on short local codes instead.
Vatican City
There's less than a thousand people in there, so in theory, their local codes might be as low as three digits? How exciting!
Alas, apparently they use numbers starting with +39 for Italy, then 06 for Rome, and then there's a bunch of digits after that, so no chance.
New Caledonia and Greenland
I found an interesting map where countries are coloured by shortest local codes.
The Wikipedia article for New Caledonia says that after its +687 country code, the shortest international option is another 6 digits, starting as low as 20. An internet search pulls up the phone number +687 20 48 20, which is pretty low at nine digits, but the first digit is quite large.
By comparison, Greenland's country code is much lower at +299, and Wikipedia says you need 6 digits after that for an international call. Searching for numbers brings up +299 32 03 33, which is lower than New Caledonia.
Falkland Islands
Now we're getting to the good stuff. Falkland Island numbers are only five digits long! Public numbers start at +500 20 XXX. I managed to find a company with this prefix. Its full phone number is +500 20 800. That's fifty million, twenty thousand and eight hundred.
Niue
Thinking I'd done the best I could, I sent this challenge to a friend and he immediately fired back with some positively svelte seven digit numbers from Niue! (Apparently you can just call up the island's tourism office on +683 4224. Wikipedia says you can call +683 101 for the weather and tidal report, but I'm not sure if it's available globally, so I can't count it.)
Saint Helena
Saint Helena used to also have 7 digit numbers, starting with +290, which would be lower than Niue. However, these were all moved to being 8 digit numbers, and the old ones don't exist any more.
The smallest phone number
The smallest one I could find is +683 4002 (info), which calls up Tutuli Heka. He used to be in charge of Niue's only phone company, so it makes sense that he'd have first dibs at a low number. That's six million, eight hundred and thirty-four thousand and two.
If you can find a smaller one than that, or even a (gasp) six digit number, I'd be really impressed. Let me know how you do!
C.