Алгоритм получает на вход натуральное число N и строит по нему новое число R следующим образом.
1. Строится троичная запись числа N.
2. В полученной записи все нули заменяются на двойки, все двойки — на нули. Из полученного числа удаляются ведущие нули.
3. Результат переводится в десятичную систему счисления.
4. Результатом работы алгоритма становится модуль разности исходного числа N и числа, полученного на предыдущем шаге.
Пример. Дано число N = 35. Алгоритм работает следующим образом.
1. Строим троичную запись числа N: 3510 = 10223.
2. Заменяем цифры и удаляем ведущие нули: 1022 → 1200.
3. Переводим в десятичную систему: 12003 = 4510.
4. Вычисляем модуль разности: |35 − 45| = 10.
Результат работы алгоритма R = 10.
При каком наименьшем N в результате работы алгоритма получится R = 1 864 246.
Приведём решение задачи на языке Python.
for N in range(1864245, 10**10):
s = ''
while N > 0:
s += str(N%3)
N //= 3
s = s[::-1]
R = s.replace('0','*').replace('2','0').replace('*','2')
if abs(int(s,3) - int(R,3)) == 1864246:
print(int(s,3))
break
Ответ: 3323607.
Приведём программу Сергея Донец на PascalABC.NET:
При малых N разность R = |M - N| также мала (как в примере с N = 35 → R = 10).
M получается заменой цифр в троичной записи N, поэтому M и N имеют сопоставимый порядок величины.
R растёт пропорционально N, но нелинейно из-за замены цифр в троичной системе.
Если N∼103 то R∼103.
Если N∼106 то R∼106.
Следовательно, R=∣M−N∣ также имеет порядок, близкий к N.
При замене всех 0 на 2 в троичной записи N, число M может увеличиться максимум в 2 раза
если N = R = 1864246 div 2, то N = 932123 M = 662199 R = 269924 подтверждается пропорциональность ∼103
чтобы не высчитывать оптимальное начало N примем N = R = 1864246 и для него высчитаем разность:
N = 1864246. получим M = 2918722 R = 1054476 (меньше требуемого почти в 2 раза), значит
N > 1864246. также подтверждается прапорциональность ∼106
Если N<1864246, то M (полученное заменой цифр) не может быть больше N+1864246, так как замена цифр в троичной системе не приводит к такому скачку. Следовательно, R=∣M−N∣ не может достичь 1864246 при N<1864246.
Перебор можно начинать и с N = 1, но оптимальнее — с N = R = 1864246, так как при N<1864246 разность заведомо меньше целевого значения.
мы и так уже съэкономили диапазон 1..1864246. Начинаем перебор с N=1864246.
Обоснование нижней границы поиска
Если N<1864246, то R заведомо меньше целевого значения, так как R≤N<1864246.
Следовательно, перебор можно начинать с N=1864246 (это экономит диапазон 1..1864246).
Оптимизация верхней границы
Верхняя граница: N≤2×1864246=3728492 (так как M≤2N, и R=M−N≤N).
Итоговый диапазон перебора: N∈[1864246,3728492].
uses School;
begin
var start := 1864246;
var koend := 1864246 * 2;
var minN := MaxInt; // Инициализация максимальным значением
for var n := start to koend do
begin
var T := ToBase(n, 3);// N в троичной системе
T := T.Translate('02', '20'); // Замена 0→2, 2→0
var M := dec(t, 3);// M = преобразованное число
var R := abs(M - N);// R = |M - N|
if R = 1864246 then
begin
minN := N < minN ? N : minN;// Обновляем минимальное N
//Println(N, M, R); // Вывод для отладки = в окончательном варианте закоментируем
end;
end;
Println(minN); // Минимальное N, дающее R = 1864246
end.