Most efficient way to store thousand telephone numbers

In what follows, I treat the numbers as integer variables (as opposed to strings):

1. Sort the numbers.
2. Split each number into the first five digits and the last five digits.
3. The first five digits are the same across numbers, so store them just once. This will require 17 bits of storage.
4. Store the final five digits of each number individually. This will require 17 bits per number.

To recap: the first 17 bits are the common prefix, the subsequent 1000 groups of 17 bits are the last five digits of each number stored in ascending order.

In total we’re looking at 2128 bytes for the 1000 numbers, or 17.017 bits per 10-digit telephone number.

Search is O(log n) (binary search) and full enumeration is O(n).