Условие

Найдите 2026-е число, представимое в виде суммы различных степеней тройки (3^0, 3^1, 3^2, ...).

Решение

Подход — биекция с двоичной записью

Числа, представимые как сумма различных степеней тройки, имеют троичное представление, в котором каждая цифра — это 0 или 1 (никогда 2). Например:

1 = 1 (цифра 1)
3 = 10
4 = 1 + 3 = 11
9 = 100
10 = 1 + 9 = 101
12 = 3 + 9 = 110
13 = 1 + 3 + 9 = 111

Если перенумеровать такие числа в порядке возрастания: 1-е → 1, 2-е → 3, 3-е → 4, 4-е → 9, 5-е → 10, ...

Биекция: n-е такое число получается, если взять двоичную запись числа n и интерпретировать её как троичную.

Проверка

n	bin(n)	как число в base-3
1	`1`	`1₃` = 1
2	`10`	`10₃` = 3
3	`11`	`11₃` = 1+3 = 4
4	`100`	`100₃` = 9
5	`101`	`101₃` = 10
6	`110`	`110₃` = 12
7	`111`	`111₃` = 13
8	`1000`	`1000₃` = 27

Совпадает.

Реализация

n = 2026
# Переводим n в двоичный вид
b = bin(n)[2:]  # '11111101010'
# Интерпретируем эти цифры как троичные
result = int(b, 3)
print(result)  # 88660

Вычисление вручную

2026 в двоичной системе:

2026 = 1024 + 1002
     = 1024 + 512 + 490
     = 1024 + 512 + 256 + 234
     = 1024 + 512 + 256 + 128 + 106
     = 1024 + 512 + 256 + 128 + 64 + 42
     = 1024 + 512 + 256 + 128 + 64 + 32 + 10
     = 1024 + 512 + 256 + 128 + 64 + 32 + 8 + 2

Степени двойки в 2026: 2^10 + 2^9 + 2^8 + 2^7 + 2^6 + 2^5 + 2^3 + 2^1

2026₂ = 11111101010 (биты на позициях 1, 3, 5, 6, 7, 8, 9, 10).

Соответствующее число — сумма 3^k для тех же k:

3^10 + 3^9 + 3^8 + 3^7 + 3^6 + 3^5 + 3^3 + 3^1
= 59049 + 19683 + 6561 + 2187 + 729 + 243 + 27 + 3
= 88482

Проверка через Python: int('11111101010', 3) = 88482.

Сложность

O(log n) — длина двоичного представления.

Подводные камни

«2-я степень тройки = 3». Нет: 3^0 = 1, 3^1 = 3. «Различные» степени включают 3^0 = 1.
Включать 0-е число. Если 0-е = 0 (пустая сумма), то наше «1-е» становится 0, и всё сдвигается. Здесь нумерация с 1.
Не путать с «троичным разложением n». Если в записи n в base-3 есть цифры 2 — это не искомое число. У искомых чисел в base-3 только 0 и 1.

Эталонный ответ

88 482. Ответ получается из int(bin(2026)[2:], 3) — двоичная запись 2026, интерпретированная как троичная.

Математика — найдите 2026-е число, представимое как сумма различных степеней тройки