2016 APMO Problems/Problem 2

Problem

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, \cdots, 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.

Solution