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 3 of 5: Small exponent case and conclusion

Previous step Next step

a_r\le100\Longrightarrow cn\le2^0+2^1+\cdots+2^{100}=n

Detailed analysis

If instead $a_r\le100$ , the binary expansion uses at most $100$ powers selected from $\{2^0,2^1,\ldots,2^{100}\}$ . Hence $cn\le2^0+2^1+\cdots+2^{100}=n$ . Since $cn$ is a positive multiple of $n$ , equality would force $c=1$ and would require all $101$ powers $2^0,\ldots,2^{100}$ to occur, impossible for a representation with at most $100$ powers. This contradiction shows that no positive multiple of $n=2^{101}-1$ is fancy, and together with the lower bound proves that this is the smallest such integer.