Maths Olympiad Prep

Library / /311 of 860

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 2n12^{n}-1. If s=2023s=2023 (in base ten), compute nn (in base ten).

A number or a short expression. Spacing and $ signs are ignored.

Solution

Every power of 2 is either represented in base 4 as 100004100 \ldots 00_{4} or 200..004200 . .00_{4} with some number of zeros. That means every positive integer in the form 2n12^{n}-1 is either represented in base 4 as 333334333 \ldots 33_{4} or 13333133 \ldots 33 for some number threes. Note that 2023=2022+1=6743+12023=2022+1=674 \cdot 3+1, meaning 2n12^{n}-1 must be 1333334133 \ldots 333_{4} with 674 threes. Converting this to base 2 results in 133334=2000041=246741=213491133 \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,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.