# Finding the smallest positive integer from the fancy number

Finding the smallest positive integer from the fancy number

Problem 2.

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

where a1,a2, … , a100 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.

(APMO 2016 problem 2)

Solution. Let k be any positive integer less than 2101 – 1. Then k can be expressed in binary notation using at most 100 ones, and therefore there exists a positive integer r and non-negative integers a1, a2, … , ar such that $\leq 100$ and k = 2a1 + … + 2ar. Notice that for a positive integer s we have:

This shows that k has a multiple that is a sum of r + s powers of two. In particular, we may take $s=100-r\geq 0$, which shows that k has a multiple that is a fancy number. We will now prove that no multiple of n = 2101 – 1 is a fancy number. In fact we will prove a stronger statement, namely, that no multiple of n can be expressed as the sum of at most 100 powers of 2.

For the sake of contradiction, suppose that there exists a positive integer c such that cn is the sum of at most 100 powers of 2. We may assume that c is the smallest such integer. By repeatedly merging equal powers of two in the representation of cn we may assume that

where $r\leq 100$ and a1 < a2 < … < ar are distinct non-negative integers. Consider the following two cases:

• If ar $\geq 101$, then 2ar – 2ar – 101 = 2ar – 101n. It follows that 2a1 + 2a2 + … + 2ar-1+ 2ar – 101 would be a multiple of n that is smaller than cn. This contradicts the minimality of c.
• If ar $\leq 100$, then {a1,…, ar} is a proper subset of {0, 1, …, 100} Then