Алгоритм получает на вход натуральное число N и строит по нему новое число R следующим образом:
1. Строится двоичная запись числа N.
2. Если число N делится на 5, в конец двоичной записи добавляется двоичный код числа 5, в противном случае в конец двоичной записи добавляется 1.
3. Если полученное на предыдущем шаге число делится на 7, в конец двоичной записи добавляется двоичный код числа 7, в противном случае в конец двоичной записи добавляется 1.
4. Результатом работы алгоритма становится десятичная запись полученного числа R.
Пример. Дано число N = 10. Алгоритм работает следующим образом:
1. Строим двоичную запись: 1010 = 10102.
2. Число 10 делится на 5, добавляем к двоичной записи код числа 5, получаем 10101012 = 8510.
3. Число 85 не делится на 7, добавляем к двоичной записи цифру 1. Получаем 101010112 = 17110.
4. Результат работы алгоритма R = 171.
Определите наибольшее возможное значение N, для которого в результате работы алгоритма получается R < 1 855 663.
Приписать к 1 справа к X означает: X * 2 + 1, всегда нечётное.
В обратную сторону: (Y - 1) / 2
N будет максимальным, если N не делится на 5 и 2 * N + 1 не делится на 7.
Берём максимальное нечётное число < 1 855 663 и начинаем двигаться вниз.
(1855661 - 1) / 2 = 927830 - не подходит, т.к. чётное.
(1855659 - 1) / 2 = 927829 - не подходит, т.к. делится на 7
1855657 сразу пропускаем, т.к. будет чётное
(1855655 - 1) / 2 = 927827 - подходит, т.к. нечётное и не делится на 7
(927827 - 1) / 2 = 463913 - подходит, т.к. не делится на 5.
Ответ: 463913
БЕЗ программирования.
С побитовыми, без явного перевода в строку бит:
mR=1855
for R0 in range(1855,1855663):
R=R0
for k in (5,7):
if R%k: R=(R <<1)|1
else: R=(R <<3)|k
if R<1855663: mR=max(mR,R0)
print(mR) рез:=463913 , ч.т.д!
def find_max_n(limit):
def get_binary(n):
return bin(n)[2:]
def append_based_on_condition(n, condition, value_if_true, value_if_false):
if condition:
return n + bin(value_if_true)[2:]
else:
return n + bin(value_if_false)[2:]
def algorithm(N):
# Step 1: Binary representation of N
binary_rep = get_binary(N)
# Step 2: Append based on divisibility by 5
binary_rep = append_based_on_condition(binary_rep, N % 5 == 0, 5, 1)
# Step 3: Convert to decimal to check divisibility by 7
decimal_value = int(binary_rep, 2)
# Append based on divisibility by 7
binary_rep = append_based_on_condition(binary_rep, decimal_value % 7 == 0, 7, 1)
# Convert final binary representation to decimal
R = int(binary_rep, 2)
return R
max_n = 0
for N in range(1, limit):
R = algorithm(N)
if R < 1855663:
max_n = N
else:
break
return max_n
limit = 1000000 # Start with a reasonably large limit for the search
max_n = find_max_n(limit)
print("Наибольшее возможное значение N:", max_n)