Обозначим через a%b остаток от деления натурального числа a на натуральное число b, а через a//b — целую часть от деления a на b.
Функция F(n), где n — неотрицательное целое число, задана следующими соотношениями:
F(n) = 0, если n = 0;
F(n) = F(n//4) + n%4, если n > 0 и n%4 < 2;
F(n) = F(n//4) + n%4 − 1, если n%4 ≥ 2.
Найдите минимальное n, для которого F(n) = 27, а F(n + 1) = 20.
Решение.
Это задание ещё не решено, приводим решение прототипа.
Обозначим через a%b остаток от деления натурального числа a на натуральное число b, а через a//b — целую часть от деления a на b.
Функция F(n), где n — неотрицательное целое число, задана следующими соотношениями:
F(n) = 0, если n = 0;
F(n) = F(n//4) + n%4, если n > 0 и n%4 < 2;
F(n) = F(n//4) + n%4 − 1, если n%4 ≥ 2.
Найдите минимальное n, для которого F(n) = 27, а F(n + 1) = 16.
Функция возвращает сумму остатков деления на 4. Чтобы получилось 27, и число n было минимальным, должно быть 13 остатков по 2 и один остаток по 1. Тогда число должно состоять из 3 и одной 2. Тогда следующее число, при прибавлении 1 получится состоящим из 3 и 0, при том, что нули пойдут на местах, где стояли 3 после 2.
Приведём решение на языке Python.
from itertools import product
for i in product('23', repeat=14):
i=''.join(i)
if i.count('3')*2 + 1 ==27:
s = i[:i.find('2')] + '3' + '0' * len(i[i.find('2')+1:])
if (s.count('3')*2) == 16:
print(int(i,4))
Ответ: 268431359.