# 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

Also Read:

where a_{1},a_{2}, … , 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.

**(APMO 2016 problem 2)**

Answer: The answer is n = 2^{101} – 1.

Solution. Let k be any positive integer less than 2^{101} – 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 a_{1}, a_{2}, … , a_{r} such that and k = 2^{a1} + … + 2^{ar}. 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 , which shows that k has a multiple that is a fancy number. We will now prove that no multiple of n = 2^{101} – 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 and a_{1} < a_{2} < … < a_{r} are distinct non-negative integers. Consider the following two cases:

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

This is also a contradiction.

From these contradictions we conclude that it is impossible for cn to be the sum of at most 100 powers of 2. In particular, no multiple of n is a fancy number.