4th Iberoamerican 1989 Problem B2 The function f on the positive integers satisfies f(1) = 1, f(2n + 1) = f(2n) + 1 and f(2n) = 3 f(n). Find the set of all m such that m = f(n) for some n.
We show that to obtain f(n), one writes n in base 2 and then reads it in base 3. For example 12 = 1100 2 , so f(12) = 1100 3 = 36. Let g(n) be defined in this way. Then certainly g(1) = 1. Now 2n+1 has the same binary expansion as 2n except for a final 1, so g(2n+1) = g(2n) + 1. Similarly, 2n has the same binary expansion as n with the addition of a final zero. Hence g(2n) = 3 g(n). So g is the same as f. Hence the set of all m such that m = f(n) for some n is the the set of all m which can be written in base 3 without a digit 2. 4th Ibero 1989 © John Scholes jscholes@kalva.demon.co.uk 1 July 2002