Решение 1

Распишем все переходы для пар из единиц и двоек.

Задача у нас про сумму цифр, как видим сумма при переходе пар константна.

Рассмотрим переходы одиночных цифр между нулями.

Как видим, сумма оба раза уменьшилась на единицу. Получается, что если изначальная сумма была , то сумма после работы алгоритма будет . Начальная сумма цифр . Нам необходимо количество единиц . Минимальное простое число большее — это , учтем единицу, которую вычитали, получаем — начальная сумма цифр и — количество единиц.

Решение 2

def is_prime(n):
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return n > 1

for n in range(101, 1000):
    s = "0" + ’2’ * 50 + ’1’ * n + ’0’
    while not (’00’ in s):
        s = s.replace(’02’, ’101’, 1)\
            .replace(’11’, ’2’, 1)\
            .replace(’012’, ’30’, 1)\
            .replace(’010’, ’00’, 1)
    if is_prime(sum(int(x) for x in s)):
        print(n)
        break