Let be the number of ways to write as a sum of powers of , where we keep track of the order of the summation. For example, because can be written as , , , , , and . Find the smallest greater than for which is odd.
Solutions — 2
Solution 1
First of all, note that = where is the largest integer such that . We let for convenience.
From here, we proceed by induction, with our claim being that the only such that is odd are representable of the form
We induct on . It is trivially true for and . From here, we show that, if the only numbers where is odd are of the form described above, then the only numbers that are odd are of that form. We first consider all numbers , such that , going from the lower bound to the upper bound (a mini induction, you might say). We know that . For a number in this summation to be odd, . However, we know that , so must be equal to , or else cannot be in that interval. Now, from this, we know that , as . Therefore, and are distinct, and thus and are odd; since there are just two odd numbers, the ending sum for any is even. Finally, considering , the only odd number is , so the ending sum is odd.
The smallest greater than expressible as is
Solution 2
Let denote the number of ways to express as a sum of powers of 2, considering the order of summation. To solve this problem, we must determine the smallest integer for which is odd.
Firstly, we understand that is related to binary representations of numbers. Each integer can be uniquely represented in base 2, meaning , where are binary digits (0 or 1). The task is to count all partitions utilizing available powers of 2, ordered permutations included.
A key insight into solving this problem is:
- if and only if is a Mersenne number, which is of the form .
To determine this, consider complete sets of powers of 2. The set of all subsets of , when considered with repetition and order, represents all sums for to .
For , the binary representation contains all 1s, i.e., with ones. Only for of this form, the number of ordered sums equates to an odd number due to properties of binomial coefficients (odd summation through subsets).
Our strategy is then to find the smallest such that .
Calculating :
For , is greater than 2013 and is odd since 2047 is a Mersenne number. Thus, this satisfies the given condition.
Therefore, the smallest for which is odd is: