Задание 25. Информатика. ЕГЭ. Поляков-5306

(А. Бычков) Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы:

• символ «\(?\)» означает ровно одну произвольную цифру;
• символ «\(*\)» означает любую последовательность цифр произвольной длины; в том числе «\(*\)» может задавать и пустую последовательность;
• символ «\(F\)» означает любое число, входящее в последовательность Фибоначчи (числа Фибоначчи – это ряд чисел, в котором первое и второе число равны единице, а каждое следующее число равно сумме двух предыдущих чисел ряда: \(1, \, 1, \, 2, \, 3, \, 5, \, 8, \, 13, \, \ldots ).\)

Найдите все натуральные числа, не превышающие \(10^9,\) которые соответствуют маске \(73{*}5F486F\) и делятся на \(43\) без остатка. В ответе запишите найденные числа в порядке возрастания, справа от каждого — соответствующее частное от деления на \(43.\)

F = [1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144]

st = 73514861 // 43 * 43
for n in range(st, 10**9, 43):
    ns = str(n)
    if ns[:2] == '73':
        end = (f'5{a}486{b}' for a in F for b in F)
        if any(ns[-len(f):] == f for f in end):
            print(n, n // 43)