## August 2015 solution

The mention of Erdős in the riddle, and specifically the reminder of his connection to last month's riddle, was actually a hint. I was referring to his result, detailed in the July solution, that any integer, y, can be represented as the sum of integers of the form 2a3b such that no two divide each other. The name given to such a representation is a d-representation.

Erdős initially posed this problem as a challenge to his friends, but, to use his own words, overestimated the difficulty of the problem. It was solved almost immediately. For completeness, let us recap the proof:

Let y be the smallest integer not representable in this way. If y is even, y=2k, multiply by 2 each number used in the representation of k. If y is odd, it must be in the range 3iy<3i+1 for some i. By subtracting 3i we either solve the problem or reduce it to an even number such that its half is less than 3i, so proceeding as in the case where y is even solves the problem.

Now, consider our generalised "3xn+1" problem. We claim that there is always a path from any n to 1. Consider what such a path looks like. I'll give, again, the example of 7, using the standard Collatz function:

(((((7*3+1)/2*3+1)/2*3+1)/22*3+1)/23*3+1)/24=1

Multiplying both sides by a high-enough power of 2 we can always make this into an integer equation. After opening the parentheses, it looks like this:

7*35+34+2*33+22*32+24*3+27=211

Under the generalised conditions we are interested in, the equation looks much the same, except for the fact that powers of three can drop rapidly from one summand to the next, whereas here they reduce by one each time. Specifically, we are trying to find, for a given n, an a and a b such that the difference 2b-n*3a has a d-representation where the highest power of 3 used is less than a.

Note, however, that for any n there will be some a for which there is a power of 2 in the range (n*3a, (n+1)*3a). (This is clear when considering the problem in log-scale, noting that log23 is irrational.) Let that power of 2 be 2b.

Because any integer has a d-representation, this will also be true specifically for 2b-n*3a. Because the difference is less than 3a, we know that any power of 3 used will necessarily be smaller than a.

Q.E.D.