Problem 2

A positive integer is called fancy if it can be expressed in the form

2^{a_1}+2^{a_2}+\cdots+2^{a_{100}}

, where

a_1,a_2,\ldots,a_{100}

are non-negative integers that are not necessarily distinct. Find the smallest positive integer

n

such that no multiple of

n

is a fancy number.

Step 4 of 5: Large exponent case for a minimal counterexample

Previous step Next step

cn=2^{a_1}+\cdots+2^{a_r},\ r\le100,\ a_r\ge101\Longrightarrow 2^{a_r}=2^{a_r-101}n+2^{a_r-101}

Detailed analysis

Suppose for contradiction that some multiple $cn$ of $n=2^{101}-1$ is fancy. Replacing repeated powers by their binary carry operation, it has a representation with at most $100$ distinct powers; choose such a representation with $c$ minimal, and let $a_r$ be its largest exponent. If $a_r\ge101$ , then $2^{a_r}=2^{a_r-101}n+2^{a_r-101}$ , so replacing $2^{a_r}$ by $2^{a_r-101}$ decreases $cn$ by $2^{a_r-101}n$ , giving a smaller positive multiple of $n$ with at most $100$ binary powers, contradicting minimality of $c$ .