Problem:
Let be the increasing sequence of positive integers whose binary representation has exactly ones. Let be the th number in . Find the remainder when is divided by .
Solution:
Because and the th integer in must have digits. There are integers in less than , and exactly of these have digits and begin with . The th integer in must be the number in position among the numbers beginning with . Of these, of them begin with , another of them begin with , and of them begin with . It follows that the largest number in beginning with must be in position among the elements of that begin with . Thus the th integer in is . This number has the value
The requested remainder when is divided by is .
The problems on this page are the property of the MAA's American Mathematics Competitions