For any positive integer , let denote the number of 1's in the base-2 representation of . For how many values of with do we have ?
Solution
If is even, then is obtained from in binary by changing the final 0 to a 1; thus . If is odd, then is obtained by changing the last 0 to a 1, the ensuing string of 1's to 0's, and then changing the next rightmost 0 to a 1. This produces no net change in the number of 1's iff ends in 01 in base 2. Thus, if and only if is congruent to , and there are 501 such numbers in the specified range.
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.