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

*На вход алгоритма подаётся натуральное число \(N.\) Алгоритм строит по нему новое число \(R\) следующим образом:

1. Строится двоичная запись числа \(N.\)
2. Если число \(N\) делится на \(3,\) в конец двоичной записи дописывается двоичный код числа \(3,\) иначе дописывается единица.
3. Если число, полученное после шага \(2,\) делится на \(5,\) в конец двоичной записи дописывается двоичный код числа \(5,\) иначе дописывается единица.
4. Полученная таким образом запись является двоичной записью искомого числа \(R.\)

Например, для исходного числа \(7_{10} = 111_2\) (не делится на \(3\)) после шага \(2\) получается число \(1111_2 = 15_{10}\) (делится на \(5\)), а после шага \(3\) – число \(1111101_2 = 125_{10}.\) Определите наибольшее возможное значение \(N,\) для которого в результате работы алгоритма получается \(R < 10^6.\)

def R(N):
    bn = f'{N:b}'
    bn += '11' if N % 3 == 0 else '1'
    bn += '101' if int(bn, 2) % 5 == 0 else '1'
    return int(bn, 2)

print(max(N for N in range(1000, 10**6) if R(N) < 10**6))