Задание EGEINFDE645A: Делители, маски и отбор чисел

Решение.
Требуются первые пять чисел, строго больших 8007524668. Начинаем с 8007524669 и рассматриваем целые n подряд в порядке возрастания.
Разложим n на простые множители. Каждый простой делитель записываем один раз, независимо от степени. Само n исключаем: если n простое, допустимых простых делителей нет и M = 0.
Пусть p — наименьший, q — наибольший из оставшихся простых делителей. Тогда M = p + q. Если простой делитель только один, минимум и максимум совпадают, поэтому M равняется удвоенному делителю; такой случай нельзя отбрасывать.
При разложении последовательно делим остаток на каждый найденный простой множитель до исчезновения его степени. Если после проверки всех p с p² ≤ остатку остаётся число больше 1, оно простое: составное число обязательно имело бы делитель не больше своего квадратного корня.
Проверяем три условия одновременно: M больше 110000, M простое, запись M содержит «991» ровно один раз. Простоту проверяем отсутствием простого делителя от 2 до ⌊√M⌋.
Здесь M простое и больше 2, значит оно нечётное. Сумма двух нечётных простых чётна, поэтому наименьший простой делитель подходящего n равен 2. Это дополнительно проверяет все найденные строки. Перебор программы всё равно включает и чётные, и нечётные n.
n = 8007539144 = 2³ · 11 · 607 · 149909.
Различные простые делители: 2, 11, 607, 149909.
M = 2 + 149909 = 149911.
149911 больше 110000; «991» встречается ровно один раз. Среди простых чисел от 2 до 387 делителей M нет, поэтому M простое.
n = 8007540788 = 2² · 13 · 153991169.
Различные простые делители: 2, 13, 153991169.
M = 2 + 153991169 = 153991171.
153991171 больше 110000; «991» встречается ровно один раз. Среди простых чисел от 2 до 12409 делителей M нет, поэтому M простое.
n = 8007540856 = 2³ · 7 · 142991801.
Различные простые делители: 2, 7, 142991801.
M = 2 + 142991801 = 142991803.
142991803 больше 110000; «991» встречается ровно один раз. Среди простых чисел от 2 до 11957 делителей M нет, поэтому M простое.
n = 8007547448 = 2³ · 101 · 9910331.
Различные простые делители: 2, 101, 9910331.
M = 2 + 9910331 = 9910333.
9910333 больше 110000; «991» встречается ровно один раз. Среди простых чисел от 2 до 3148 делителей M нет, поэтому M простое.
n = 8007550626 = 2 · 3 · 8839 · 150989.
Различные простые делители: 2, 3, 8839, 150989.
M = 2 + 150989 = 150991.
150991 больше 110000; «991» встречается ровно один раз. Среди простых чисел от 2 до 388 делителей M нет, поэтому M простое.
В программе решето строит простые числа до 100000. Перебор ограничен сверху 10¹⁰, чей квадратный корень равен 100000, поэтому списка достаточно для полного разложения каждого проверяемого n и проверки простоты M. Ниже показано, что все пять результатов найдены раньше этой границы; после пятого программа сразу завершается.
Полный последовательный перебор от 8007524669 до 8007550626 включительно проверяет 25958 чисел. Условие выполняется ровно для пяти перечисленных n. Все меньшие допустимые кандидаты проверены, поэтому это именно первые пять чисел.
Проверка результата.
Воспроизводимая программа Python:

from math import isqrt
from operator import gt, lt

limit = 100000
flags = [True] * (limit + 1)
flags[0] = flags[1] = False
for p in range(2, isqrt(limit) + 1):
    if flags[p]:
        for multiple in range(p * p, limit + 1, p):
            flags[multiple] = False
primes = [p for p in range(2, limit + 1) if flags[p]]

def prime_divisors(n):
    rest = n
    result = []
    for p in primes:
        if gt(p * p, rest):
            break
        if rest % p == 0:
            result.append(p)
            while rest % p == 0:
                rest = divmod(rest, p)[0]
    if rest != 1:
        result.append(rest)
    return [] if result == [n] else result

def is_prime(n):
    if lt(n, 2):
        return False
    for p in primes:
        if gt(p * p, n):
            return True
        if n % p == 0:
            return False
    return True

found = 0
for n in range(8007524669, 10 ** 10 + 1):
    d = prime_divisors(n)
    M = d[0] + d[-1] if d else 0
    if gt(M, 110000) and str(M).count('991') == 1 and is_prime(M):
        print(n, M)
        found += 1
        if found == 5:
            break
assert found == 5

Результат: в каждой строке слева n, справа M.
8007539144 — 149911
8007540788 — 153991171
8007540856 — 142991803
8007547448 — 9910333
8007550626 — 150991
Ответ: (8007539144; 149911), (8007540788; 153991171), (8007540856; 142991803), (8007547448; 9910333), (8007550626; 150991).