Задание №12 — Анализ строковых алгоритмов

Решение:

Посмотрим на роль символа «>». Замены >2 → >3 и >3 → >1 меняют цифру на месте, не сдвигая указатель, и только замена >1 → 1> пропускает цифру влево от указателя, после чего она уже не изменяется.

Значит любая цифра, стоящая за указателем, доводится до единицы: тройка становится единицей, двойка сначала становится тройкой, а потом единицей. В итоге вся строка состоит из единиц, и сумма цифр просто равна их количеству: $$16 + n + 16 = 32 + n.$$

Перебираем $n$: $33 = 3 \cdot 11$, $34$, $35 = 5 \cdot 7$, $36$ — составные, а $32 + 5 = 37$ — простое число. Наименьшее подходящее $n = 5$.

def zamenit(s, v, w):
    return s.replace(v, w, 1)   # первое слева вхождение

def prostoe(x):
    d = 2
    while d * d <= x:
        if x % d == 0:
            return False
        d += 1
    return x > 1

def rabota(s):
    while ">1" in s or ">2" in s or ">3" in s:
        if ">1" in s:
            s = zamenit(s, ">1", "1>")
        if ">2" in s:
            s = zamenit(s, ">2", ">3")
        if ">3" in s:
            s = zamenit(s, ">3", ">1")
    return s

n = 1
while True:
    s = rabota(">" + "1" * 16 + "2" * n + "3" * 16)
    summa = sum(int(c) for c in s if c != ">")
    if prostoe(summa):
        print(n, summa)   # 5 37
        break
    n += 1