Maths Olympiad Prep

Library / HMMT February /367 of 1302

HMMT February

Number theory Difficulty 5.1 AIME, harder Find the answer

Let nn be a positive integer, and let ss be the sum of the digits of the base-four representation of 2n−12^{n}-1. If s=2023s=2023 (in base ten), compute nn (in base ten).

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Every power of 2 is either represented in base 4 as 100…004100 \ldots 00_{4} or 200..004200 . .00_{4} with some number of zeros. That means every positive integer in the form 2n−12^{n}-1 is either represented in base 4 as 333…334333 \ldots 33_{4} or 133…33133 \ldots 33 for some number threes. Note that 2023=2022+1=674⋅3+12023=2022+1=674 \cdot 3+1, meaning 2n−12^{n}-1 must be 133…3334133 \ldots 333_{4} with 674 threes. Converting this to base 2 results in 133…334=200…004−1=2⋅4674−1=21349−1133 \ldots 33_{4}=200 \ldots 00_{4}-1=2 \cdot 4^{674}-1=2^{1349}-1 for an answer of 1349.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.