Счастливые IPv4 адреса: сколько их и как я их считал?
Привет всем!
Недавно я задался вопросом, про IPv4 адреса и решил поделиться с вами. Как вы знаете, IPv4 адреса состоят из четырех чисел от 0 до 255 (например, 192.168.0.1). Но вот что меня зацепило: существует понятие "счастливых" IPv4 адресов. Это как счастливый билетик в автобусах раньше.
"Счастливый" IPv4 адрес - это такой адрес, в котором сумма цифр в первых двух числах равна сумме цифр в последних двух числах. Например, адрес 176.9.136.58 является "счастливым", потому что: 1 + 7 + 6 + 9 = 23 1 + 3 + 6 + 5 + 8 = 23
Теперь главный вопрос: сколько всего может быть таких "счастливых" IPv4 адресов? Я решил разобраться и вот как я подошел к этой задаче.
Решение задачи
Первый подход: в лоб
Для начала я решил попробовать простой способ. Я написал программу, которая генерировала все возможные комбинации IPv4 адресов и проверяла их "счастливость". Вот код на Python:
# Функция для вычисления суммы цифр в числе
def sum_of_digits(n):
return sum(int(digit) for digit in str(n))
# Перебор всех возможных IP-адресов и запись счастливых IP в файл
happy_ip_count = 0
happy_ips = []
with open('happy_ips.txt', 'w') as file:
for octet1 in range(256):
for octet2 in range(256):
for octet3 in range(256):
for octet4 in range(256):
left_sum = sum_of_digits(octet1) + sum_of_digits(octet2)
right_sum = sum_of_digits(octet3) + sum_of_digits(octet4)
if left_sum == right_sum:
happy_ip = f"{octet1}.{octet2}.{octet3}.{octet4}"
happy_ips.append(happy_ip)
print(f"Found happy IP: {happy_ip}")
file.write(f"{happy_ip}\n")
happy_ip_count += 1
print(f"Total number of happy IP addresses: {happy_ip_count}")
Этот метод был простым, но медленным. Проверка всех возможных комбинаций заняла несколько часов. А пока программа работала, у меня появилось время подумать над оптимизацией кода.
Второй подход: оптимизированный
Я предварительно подсчитал количество пар октетов, дающих определенную сумму цифр. Вот как это выглядело:
import itertools
def sum_of_digits(n):
return sum(int(digit) for digit in str(n))
sum_pairs_count = [0] * 39
for a, b in itertools.product(range(256), repeat=2):
sum_pairs_count[sum_of_digits(a) + sum_of_digits(b)] += 1
happy_ip_count = sum(count ** 2 for count in sum_pairs_count)
print(f"Total number of happy IP addresses: {happy_ip_count}")
Этот метод оказался намного быстрее, так как я заранее посчитал суммы цифр для всех пар октетов и использовал эти данные для подсчета "счастливых" адресов.
Подробное объяснение процесса
Чтобы лучше понять, как работает второй подход, я объясню его шаг за шагом.
Функция для вычисления суммы цифр в числе:
def sum_of_digits(n): return sum(int(digit) for digit in str(n))
Эта функция принимает число и возвращает сумму его цифр. Например, для числа 176 она вернет 1 + 7 + 6 = 14.
2. Подсчет сумм цифр для пар октетов:
Я использовал цикл для генерации всех возможных пар чисел от 0 до 255 и подсчета суммы их цифр. Эти данные я сохранял в массив sum_pairs_count, где индекс представляет собой сумму цифр, а значение - количество пар октетов с такой суммой.
sum_pairs_count = [0] * 39 # Максимальная сумма цифр для двух октетов = 2 * 19 = 38
for a, b in itertools.product(range(256), repeat=2):
sum_pairs_count[sum_of_digits(a) + sum_of_digits(b)] += 1
3. Подсчет счастливых IP-адресов:
Для каждого возможного значения суммы цифр я подсчитал количество счастливых адресов, возведя в квадрат количество пар октетов с этой суммой. Это связано с тем, что для каждой пары октетов (octet1, octet2) с одинаковой суммой цифр должна существовать пара (octet3, octet4) с той же суммой.
happy_ip_count = sum(count ** 2 for count in sum_pairs_count)
Математическое объяснение
IPv4 адреса можно представить как комбинацию четырех октетов: A.B.C.D, где A,B,C,D∈[0,255]. Сумма цифр для каждого октета находится в пределах от 0 до 19. Таким образом, сумма цифр двух октетов (например, A и B) варьируется от 0 до 38. Мы вычисляем количество пар октетов для каждой возможной суммы цифр и затем подсчитываем количество счастливых IP-адресов.
Статистика счастливых IP-адресов
Согласно данным IANA, многие IP-адреса уже заняты или зарезервированы для специальных нужд. Однако, даже с учетом занятых адресов, количество счастливых адресов остается значительным.
Итоги
После всех вычислений и оптимизаций мне удалось определить, что общее количество "счастливых" IPv4 адресов составляет 215,397,594. При общем числе IPv4 адресов, равном 4,294,967,296, это составляет приблизительно 5%, что означает, что вероятность получить такой адрес составляет один к двадцати. Однако, даже при такой высокой вероятности, скорее всего ваш адрес обычный.
P.S.