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.
A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.
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 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: NuminaMath-1.5,
licensed Apache-2.0.
Statement and solution reproduced as published; topic and difficulty added by this site.