Сумма, простота и ограничения на количества

Дополнительный урок — для продвинутых: такие вопросы редки.

Таблица ниже один раз проходит строку из цифр 3, 6, 9 и заменяет 3 → 7, 6 → 8, 9 → 3. Как связаны длина входа и сумма цифр результата?

При однократной замене сумму результата выражают через количества входа — порядок цифр на неё не влияет. Пусть во входе a троек, b шестёрок и c девяток. Длина N = a + b + c, сумма результата S = 7a + 8b + 3c, и S + N = 8a + 9b + 4c. Дальше перебирают количества, а не строки.

Во входе есть все три цифры, а нечётных (3 и 9) не меньше пяти. Каково наименьшее S + N?

Чтобы сумма была наименьшей, берут ровно столько цифр, сколько требует условие, и самые дешёвые из них. Шестёрка нужна одна (b = 1): она ничего не даёт для условия о нечётных. Из нечётных девятка дешевле тройки (4 против 8), но одна тройка обязательна: a = 1, c = 4. S + N = 8 + 9 + 16 = 33, например 369999 → 783333.

Длина входа не больше 10, нечётных цифр не меньше четырёх. Каково наибольшее S + N?

Чтобы сумма была наибольшей, всю длину заполняют самыми дорогими цифрами — кроме мест, которые требует условие. Дороже всех шестёрка (9), но она чётная. Ровно четыре места — нечётным, из них дороже тройка (8): a = 4, b = 6. S + N = 32 + 54 = 86, например 3333666666.

Какова наименьшая длина входа, в котором есть все три цифры, шестёрок чётное число, а сумма результата — простое число?

Простоту проверяют для каждой допустимой суммы: простое число больше 1 и делится только на 1 и на себя, а делители достаточно искать до √x. При N = 3 шестёрка одна — нечётно. При N = 4 шестёрок две: S = 7 + 16 + 3 = 26 — составное. При N = 5 шестёрок две, а троек и девяток 1 и 2: S = 7 + 16 + 6 = 29 — простое. Ответ 5, например 36699.

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

for n in range(3, 20):    found = []    for a in range(1, n):        for b in range(1, n - a):            c = n - a - b            s = 7 * a + 8 * b + 3 * c            if b % 2 == 0 and is_prime(s):                found.append((a, b, c, s))    if found:        print(n, found)        break

• Суммачерез количества: S = 7a + 8b + 3c
• Наименьшееграница + самые дешёвые цифры
• Наибольшеедлина — самыми дорогими цифрами
• Простоебольше 1, делители до √x
• Примерстрока, на которой ответ достигается