Назовём порождающим для двух последовательных простых \(p_1 < p_2\) наименьшее натуральное число, что оно закачивается на \(p_1\) и при этом делится на \(p_2\). Необходимо найти сумму порождающих для всех \(p_1 \in \left[ 5; 10^6 \right]\)

Например, если \(p_1 = 19\), то следующее простое \(p_2 = 23\). Тогда порождающим будет число \(1219\), при этом \(1219 \: \vdots \: 23\).

Полное условие можно найти тут

Несмотря на то, что сложность задачи 45%, для её решения достаточно выписать условие.

Пусть \(p_1\) содержит в себе \(k\) цифр, т.е. \(n = r \cdot 10^k + p_1\), где \(r\) — какое-то натуральное число с отрезка \(\left[ 1; p_2-1 \right]\)

Давайте посчитаем остатки по модулю \(p_2\): \(n \equiv r \cdot 10^k + p_1 \equiv 0\). Отсюда получим явную формулу для \(r\):

$$ r \equiv -p_1 \cdot 10^{-k} \equiv -p_1 \cdot 10^{p_2 -1-k} $$

Комментарии:

  1. Так как \(a^p \equiv a \mod p\), то верно что \(a^{-k} \equiv a^{p -1-k} \mod p\)
  2. Это всё бессмысленно, если не знать про алгоритм быстрого возведения в степень, который делает асимптотическую сложность возведения в степень логарифмической.

У нас есть явная формула для порождающего, и мы знаем как её быстро посчитать. Ниже приведён код на Python с использованием sympy.

from sympy import primerange  # для получения простых чисел

# быстрое возведение в степень по модулю
def fast_pow(x, y, modulo):
    if y == 0:
       return 1
    p = fast_pow(x, y // 2, modulo)
    p = (p * p) % modulo
    if y % 2:
        p = (p * x) % modulo
    return p

# нам нужно первое простое, которое больше 10^6 -- 10^6+3
primes = list(primerange(5,10**6+4)) 

sm = 0

for i in range(len(primes) - 1):
    digs = len(str(primes[i])) # количество цифр
    r = (primes[i+1]**2  - primes[i] * fast_pow(10, primes[i+1] - 1 - digs, primes[i+1])) % primes[i+1]
    sm += r * 10**digs + primes[i]

print('Result is {}'.format(sm))

Ответ: 18613426663617118