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 2 of 5: Every smaller

k

has a fancy multiple

Previous step Next step

2^s k=2^{a_1+s}+\cdots+2^{a_r+s},\quad s=100-r;\quad 2^j=2^{j-1}+2^{j-1}\text{ increases the number of powers by one}

Detailed analysis

First multiply the binary expansion of $k$ by $2^s$ , where $s=100-r$ . If $s=0$ , this already is a sum of exactly $100$ powers of two. If $s>0$ , repeatedly split one term by $2^j=2^{j-1}+2^{j-1}$ , choosing a term with positive exponent at each split; starting from the term $2^{a_r+s}$ , this can be done $s$ times and increases the number of summands from $r$ to $r+s=100$ without changing the value. Thus $k$ has a fancy multiple, so the smallest $n$ with no fancy multiple must satisfy $n\ge2^{101}-1$ .