Én ezt megnézném:
https://en.wikipedia.org/wiki/Variable-length_quantity
Ezzel már jelentősen előrébb vagy, mintha minden telefonszámhoz 16 byte kéne. 15 jegyű számot már 8 byte-on tudsz tárolni, ha jól számoltam.
Persze még lehet lejjebb menni valamivel, ha olyan feltételezéseket teszel, hogy minden szám legalább n számjegyből áll, és akkor az első n számjegyet nem VLQ-ben, hanem normál valahány byte-os int-ként tárolod.