Maths Olympiad Prep

Library / /248 of 860

Number theory Difficulty 5.0 AIME, harder Find the answer

For any positive integer nn, let f(n)f(n) denote the number of 1's in the base-2 representation of nn. For how many values of nn with 1n20021 \leq n \leq 2002 do we have f(n)=f(n+1)f(n)=f(n+1)?

A number or a short expression. Spacing and $ signs are ignored.

Solution

If nn is even, then n+1n+1 is obtained from nn in binary by changing the final 0 to a 1; thus f(n+1)=f(n)+1f(n+1)=f(n)+1. If nn is odd, then n+1n+1 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 nn ends in 01 in base 2. Thus, f(n+1)=f(n)f(n+1)=f(n) if and only if nn is congruent to 1mod41 \bmod 4, 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.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.