The function f on the positive integers satisfies f(1)=1, f(2n+1)=f(2n)+1 and f(2n)=3f(n). Find the set of all m such that m=f(n) for some n.
Solution
Solution:
We show that to obtain f(n), one writes n in base 2 and then reads it in base 3. For example, 12=11002, so f(12)=11003=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)=3g(n). So g is the same as f. Hence the set of all m such that m=f(n) for some n is the set of all m which can be written in base 3 without a digit 2.
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.
Source: MathNet,
licensed CC-BY-4.0.
Statement reproduced verbatim; metadata (topic, difficulty) added by this project.