Problem

Source: Ukrainian Mathematical Olympiad 2024. Day 1, Problem 10.2

Tags: number theory, algebra, power of 2



You are given a positive integer $n$. Find the smallest positive integer $k$, for which there exist integers $a_1, a_2, \ldots, a_k$, for which the following equality holds: $$2^{a_1} + 2^{a_2} + \ldots + 2^{a_k} = 2^n - n + k$$ Proposed by Mykhailo Shtandenko