How many natural numbers smaller than $ 2017 $ can be uniquely (order of summands are not relevant) written as a sum of three powers of $ 2? $ Andrei Eckstein
Problem
Source: Stars of Mathematics 2017, Juniors, Problem 1
Tags: number theory
sarjinius
04.02.2022 12:27
We call a number good if it can be uniquely expressed as a sum of three (integer) powers of $2$.
Note that every good number must have at most three $1$’s in its binary representation.
If a number has exactly three $1$’s in its binary representation, then it is a sum of three distinct powers of $2$.
It must be a good number since if it can be expressed in another way as a sum of three powers of $2$, then either the positions of the $1$’s would be different, or there would be less than three $1$’s in its binary representation.
If a number has exactly two $1$’s in its binary representation, then it can be expressed as $2^a + 2^b$ where $a > b \ge 0$ (thus, $a \ge 1$).
If $b \ge 1$, then $2^a + 2^b = 2^{a-1}+2^{a-1}+2^b=2^a+2^{b-1}+2^{b-1}$, so it is not good.
If $b=0$, then $2^a + 1 = 2^{a-1}+2^{a-1}+2^0$. Assume there is another way to express $2^a+1$ as a sum of three powers of $2$. Since $2^a+1$ is odd, then there should be an odd number of $2^0$’s in the sum. If $a=1$, then $3=1+1+1$ which is obviously the only way to express $3$ as a sum of three powers of $2$, so $3$ is good.
If $a \ge 2$, then $2^a \ge 4 > 3$, so there can only be one $2^0$ in the sum. Thus, there should be two nonnegative integers $m$ and $n$ such that $2^a = 2^m+2^n$ and $(m, n) \ne (a-1, a-1)$. If $m=n$, then both have to be $a-1$, contradiction. So $m \ne n$. WLOG $m > n$, then $2^{m-n}+1$ is an odd factor of $2^a$ greater than $1$, contradiction.
Hence, all numbers in the form $2^a + 1$ where $a \ge 1$ are good.
If a number has exactly one $1$ in its binary representation, then it must be in the form $2^a$ where $a \ge 0$. Note that for $a=0,1$, $2^a < 3 = 2^0+2^0+2^0$, so they are not good.
For $a \ge 2$, we have $2^a = 2^{a-1} + 2^{a-2} + 2^{a-2}$. If there is another way to express $2^a$ as a sum of three powers of $2$, then they should not be pairwise distinct, for there will be three $1$’s in the binary representation. Thus, at least two of them are equal, so there must be a way to express $2^a$ as a sum of two powers of $2$. But as shown earlier, the only way to express $2^a$ as a sum of two powers of $2$ is $2^{a-1}+2^{a-1}$, so the only way to show $2^a$ as a sum of three powers of two is $2^a = 2^{a-1} + 2^{a-2} + 2^{a-2}$.
Thus, $2^a$ is good for all integers $a \ge 2$.
Since $2^{10} < 2017 < 2^{11}$, there must be at most $11$ digits in the binary representation of the number. But the integers from $2017$ to $2047$ also have $11$ digits in their binary representations, so we have to check if any of them are good.
Fortunately, $2^{10}<2^{10}+1<2^{10}+2^9+2^8<2017<2047<2^{11}$, so none of them are good.
There are $\binom{11}{3}=165$ good numbers less than $2017$ which are sums of three distinct powers of $2$.
If $2^a+1 < 2017$ and $a \ge 1$, then $a = 1,2,\dots, 10$. Hence, there are $10$ good numbers less than $2017$ in the form $2^a+1$.
If $2^a < 2017$ and $a \ge 2$, then $a = 2,3,\dots, 10$. Hence, there are $9$ good numbers less than $2017$ in the form $2^a$.
Therefore, there are $165+10+9=\boxed{184}$ good numbers less than $2017$.