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 3i≤y<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:
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:
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.
Back to riddle
Back to main page