25.04 Основная теорема арифметики

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

Здесь – некоторое простое число, а – натуральный показатель степени. В таком случае число обязательно имеет делителей (каждое простое число можно брать от 0 до раз, где ).

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

Получается, раз всего делителей , то произведение всех состоит максимум из множителей, каждый из которых равен . Либо множителей меньше, и тогда какой-то множитель будет увеличен в раза за счёт убранного. Тогда все степени простых чисел, которые участвуют в разложении, будут иметь нечётный показатель среди чисел (степени числа от до с вычетом ).

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

Больше простых чисел брать не нужно, так как максимум в числе должно быть множителей , что означает максимальное количество простых множителей .

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

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))  # Выводим минимальное число и его простые делители