Как решить задачу объединения чисел по префиксу?
Посмотрите в сторону Radix Sort. Можно остановиться на этапе, когда выбирается разряд числа, по которому нужно сортировать. Или же начинать сортировку со старших разрядов. И когда будет распределение по корзинам (buckets), получим числа с одинаковым префиксом. Как вариант, можно таким способом попробовать.
Непонятно. Если в списке есть номер 123 и весь блок 1230, 1231,... 1239, то что будет после замены блока на префикс? Два номера 123?
А если 123 уже получился, как общий префикс 5-значных номеров?
И, кстати, в описании говорится, что делать, когда в списке уже есть префиксы. А откуда возьмётся первый префикс, когда есть только номера?
Если я правильно понял, то надо делать так.
1) сортируем номера по длинам, а внутри каждой длины - по возрастанию.
2) просматриваем номера по порядку. Если встретился номер, оканчивающийся на один или несколько нулей - то проверяем, является ли он началом блока с общим префиксом (просматривая последующие номера до первого сбоя). При этом для номера, кончающегося на один нуль, блок может иметь длину 10; для номера, кончающегося на два нуля - 10 или 100, и т.п. Самый длинный из обнаруженных блоков заменяем на префикс. 
Всё. Никакого перебора и никакой рекурсии, только сортировка и линейный просмотр.