Обозначим через 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.
Приведём аналитическое решение Данила Лукиных.
Функция возвращает сумму цифр числа n в четверичной системе счисления, но при этом цифры больше двух(то есть 2 и 3) уменьшает на единицу.
Разберёмся в каком случае сумма цифр числа в четверичной системе может уменьшиться на 11 единиц, с учётом вычета единицы из двоек и троек.
Заметим, что сумма цифр числа уменьшается при прибавлении тогда и только тогда, когда в разряде к которому её прибавляют стоит цифра - максимальная в данной системе счисления. В нашем случае это цифра 3. Значит, чтобы сумма цифр уменьшилась, изначальное число должно оканчиваться тройками.
Рассмотрим как меняется сумма цифр в зависимости от цифры, которая будет стоять перед последней тройкой:
103 (сумма 3) -> +1 -> 110 (сумма 2) -> Ноль перед тройкой приводит к добавлению единицы в новую сумму
113 (сумма 4) -> +1 -> 120 (сумма 2) -> Единица перед тройкой не меняет новую сумму
123 (сумма 4) -> +1 -> 130 (сумма 3) -> Двойка перед тройкой также приводит к добавлению единицы в новую сумму
С учётом этого, составим такую последовательность цифр, которая будет максимальна(сумму цифр для первого числа нужно «набрать» как можно быстрее) и приведёт к изменению ровно на -11
Получим 2333333 (сумма 13) -> +1 -> 3000000(сумма 2)
Значит число должно оканчиваться последовательностью 2333333, при этом оставшаяся часть числа должна «дать» сумму цифр 27 - 13 = 14. Самый быстрый способ набрать такую сумму - тройками, с учётом вычета единицы их понадобится ровно 14 / 2 = 7
Получаем число 33333332333333
Проверим:
33333332333333 (сумма 27) -> +1 -> 33333333000000 (сумма 16)
Осталось перевести число в 10-ричную систему счисления:
print(int('33333332333333', 4))