Задача к ЕГЭ по информатике на тему «делители числа» №8

Назовём числа $a$ и $b$ числами-близнецами, если $|a − b| = 2$ .

Найдите наименьшее натуральное число, имеющее ровно 512 делителей, простые делители которого образуют не менее трёх пар чисел-близнецов. В ответе укажите число, а также все его простые делители.

По основной теореме арифметики (ОТА) каждое натуральное число, большее 1, можно разложить на простые множители. То есть некоторое натуральное число $x$ можно разложить в следующий вид:

x = p1q1 ⋅p2q2 ⋅...⋅pnqn

Здесь $pi,i ∈ [1;n]$ – некоторое простое число, а $qi,i ∈ [1;n]$ – натуральный показатель степени. В таком случае число обязательно имеет $(q1 + 1)⋅(q2 + 1)⋅...⋅(qn + 1)$ делителей (каждое простое число можно брать от 0 до $qi$ раз, где $i ∈ [1;n]$ ).

Теперь перейдём к решению задачи. Необходимо найти наименьшее натуральное число, имеющее ровно $512$ , то есть $29$ делителей. При этом простые делители должны образовать не менее $3$ пар чисел-близнецов.

Получается, раз всего делителей $29$ , то произведение всех $q i$ состоит максимум из $9$ множителей, каждый из которых равен $2$ . Либо множителей меньше, и тогда какой-то множитель будет увеличен в $2$ раза за счёт убранного. Тогда все степени простых чисел, которые участвуют в разложении, будут иметь нечётный показатель среди чисел $[1,3,7,15,31,63,127,255,511]$ (степени числа $2$ от $1$ до $9$ с вычетом $1$ ).

Если число должно быть минимальным, то оно раскладываться в минимальное произведение простых чисел. Тогда выпишем первые 9 простых чисел по возрастанию:

2,3,5,7,11,13,17,19,23

Больше $9$ простых чисел брать не нужно, так как максимум в числе должно быть $9$ множителей $(q + 1) i$ , что означает максимальное количество простых множителей $9$ .

Так как каждому из $9$ простых чисел можно дать любую степень от $0$ до $511$ (всего $10$ вариантов), а также всего простых чисел ровно $9$ , то при обычном комбинаторном переборе (например при использовании product) будет получено $9 10$ вариантов разложения, что очень много и явно избыточно для получения минимального требуемого числа. Поэтому решим задачу с использованием рекурсивной функции, которая будет прекращать своё выполнение при нарушении условия по количеству делителей.

primes = [2, 3, 5, 7, 11, 13, 17, 19, 23]  # Необходимые простые числа
degrees = [1, 3, 7, 15, 31, 63, 127, 255, 511]  # Возможные показатели степеней (кроме 0)
ans = []  # Список, в который будут добавляться подходящие числа и их простые делители


# Рекурсивная функция для получения возможных чисел
# Аргументы:
#   index - индекс простого числа из списка primes
#   num - текущее полученное число
#   num_primes - простые делители, входящие в разложение числа num
#   divs_count - текущее количество делителей числа num
#   twins_count - количество чисел-близнецов среди простых делителей
def F(index, num, num_primes, divs_count, twins_count):
    # Превысили требуемое количество делителей
    if divs_count > 512:
        return  # Выход из рекурсии

    # Все простые числа были рассмотрены (взята их степень от 0 до 511)
    if index == len(primes):
        if divs_count == 512 and twins_count >= 3:  # Проверка выполнения условий
            ans.append((num, *num_primes))  # Добавляем число и его делители в список
        return  # Выход из рекурсии

    # Запуск рекурсии при отсутствии текущего простого числа primes[index] (степень 0)
    # Здесь изменяется только индекс (index+1) для взятия следующего простого числа
    F(index + 1, num, num_primes, divs_count, twins_count)

    p = primes[index]  # Текущее взятое простое число
    # Проверка наличия новой пары чисел-близнецов
    if len(num_primes) > 0 and p - num_primes[-1] == 2:
        twins_count += 1
    # Перебор показателей степеней от 1 до 511
    for q in degrees:
        new_num = num * p ** q  # Новое число
        new_num_primes = num_primes + [p]  # Список простых делителей нового числа
        new_divs_count = divs_count * (q + 1)  # Количество делителей нового числа
        # Запуск рекурсии для нового числа и его параметров
        F(index + 1, new_num, new_num_primes, new_divs_count, twins_count)














































































































































































































# Запускаем рекурсию
# Исходные параметры:
#   index = 0, так как индексация в списке начинается с 0
#   num = 1, так как для получения произведения нужно брать 1
#   num_primes = [], так как простых чисел ещё нет (они будут добавляться в список)
#   divs_count = 1, так как для получения произведения нужно брать 1
#   twins_count = 0, так как ещё нет простых чисел в разложении числа
F(0, 1, [], 1, 0)

print(*min(ans))  # Выводим минимальное число и его простые делители

Ответ: 17297280 2 3 5 7 11 13