Add divisor

[archimedes1]

Suppose you start with the number and go through a series of steps, where at each step you add a (positive integer) divisor of your current number to the number itself, to get a new number. For instance, the first step is forced: you have to take , so your new number is . Now you have two choices; the next number could be or . If you choose 4, the next step after that can take you to , , or .

a) Show that if , then you can always reach using
steps or fewer.

b) Show that if and you can reach in steps, then is a
sum of two powers of two.

[CatalystOfNostalgia]

a

Note that this is not true for , for one step is required to reach 2. We prove by induction on that for all such that , we can reach in steps or fewer, as long as . For the base case, consider , so that . 2 can be reached in 1 step, by taking simply . 3 can be reached in two steps, by taking . 4 can be reached in two steps, by taking . Since , this establishes the base case.

Now, assume the claim holds for some ; we wish to prove it for . We have that . First, if is even, we have that is an integer between and inclusive. Thus, by the inductive hypothesis, can be reached in at most steps. Then, we can get from to simply by adding , so in total this takes at most steps. Now, if is odd, we have that is an integer between and inclusive (in fact, it is strictly less than ). Thus, by the inductive hypothesis, can be reached in at most steps. Then, we can add , then add 1, to get , in at most 2 more steps, so steps total. This completes the proof.

b

We proceed by induction on . First, we show that . Let be the number after steps. We have that , and it follows that .

We first prove the claim for . That is, if and we can reach in 1 step, then is the sum of two powers of 2. is the only number that satisfies this, and . Now, assume the claim holds for some . That is, if and we can reach in steps, is the sum of two powers of two. Say that . If , we have , contradiction. Also, if one of , say , is more than , then we have , contradiction. Thus, one of them, say , is equal to exactly. So we have .

We now prove that it holds for . Let the number be , so that , and we can get to in steps. Consider the number that we have after steps; we have , so . Also, since this is the maximum number we can get to in steps. Thus, by the inductive hypothesis, is the sum of two powers of two, and we can write it as , where . We consider a few cases: first, if , note that other than itself, the largest factor of is at most . But if we add this to get to , we get , contradiction. Thus, we need to double to get , giving , obviously a power of 2.

Now, consider the case . We have , and we need to add a factor more than to get . However, the three largest factors of are , and . Thus, we can only add or . Adding results in , and adding results in , both of which are sums of two powers of two. Finally, it's left to check the case , in which we have . Any factor of is a power of 2, so adding it to results in the sum of two powers of two. This exhausts all cases, and we have completed the inductive step; is always the sum of two powers of two, as desired.

[perfect628]

Hmm I can't seem to find the file with my solutions...Here's a badly written outline, without induction!

Part a

First note that if , we simply double times to reach . Otherwise, consider the binary representation, , of . Note that because , this number has at most nonzero digits. Consider the highest such that . Note that . Then, double 1 times, so that the number is . Then, take the greatest such that . Add to the number, which can be done since divides if . Continue in this manner until is reached. There are at most 1-digits besides the initial digit, so we need at most of these steps. Therefore, to reach , we need at most steps, QED.

b

Define a -factor step as a step which adds a divisor of value times the previous number, i.e. which multiplies the number by .

We claim that the only combinations of steps which give a value of in or fewer steps are 2-factor steps followed by any other step, or 2-factor steps and two -factor steps. It is straightforward to show that each of these indeed gives a value above , and also gives a sum of two powers of two. To show that no other combinations of steps work, divide into two cases based on the number of 2-factor steps-- or less or --and show that they can't give .

Yeah that wasn't very coherent, and I don't really feel like typing it up again...I'll post my full solution if I can track down that file...

[archimedes1]

Click to reveal hidden content

PART A
First, we can clearly reach in steps by adding our number to itself at each step. Next, letting for some nonnegative integer , we wish to show that at most more steps from are required to get to . Since , we have . Since is clearly obtainable (by simply adding to itself), we need only consider .

In this case, has at most digits in its binary expansion. Then we have for distinct exponents with and , where for all . Thus, since for all , we can simply add at the th step, so that we reach after the th step. Since , we are done, as desired.

PART B
Let be the sequence of numbers obtained after steps, with .
Define a "subpar'' step to be any step in which the number is not added to itself; that is, if undergoes a subpar step, then . Then if undergoes a subpar step, then the divisor that is added during the step is at most , so we have .
In our sequence of steps, we claim that we can have at most two subpar steps. If our sequence has three or more subpar steps, then we have , which is a contradiction, as . Thus, our sequence has at most two subpar steps.

If our sequence has no subpar steps, , as desired.

Note that a subpar step from to is adding , where is some factor of . This is equivalent to multiplying by . Thus, if our sequence has exactly one subpar step, then is an integer, then must divide , so for some (if then the step is not subpar.) Thus, , as desired.

Finally, if our sequence has two subpar steps, then the subpar steps are either (1) both multiplying by , (2) multiplying by something smaller. In the first case, we have , as desired. In the second case, we have , which is a contradiction as . Moreover, we have that the third case will also produce an which is less than , giving a contradiction.

Thus, if , then must be the sum of two powers of 2.

[Criticalline1859]

Consider N in binary, it helps with the visualization of the solution (e. g. doubling is just adding a 0 at the end...).