Problem 3

For positive integer

k

, let

f(k)

be the number of integers in

\{k+1,\ldots,2k\}

whose binary expansion has exactly three

1

s. Prove every positive integer

m

occurs as

f(k)

, and determine all

m

for which exactly one

k

has

f(k)=m

Step 2 of 5: Prove every positive value occurs

Previous step Next step

In plain words

Prove every positive value occurs

2^r+2^s+1\quad(r>s>0)

Detailed analysis

The numbers $2^r+2^s+1$ have exactly three $1$ s for $r>s>0$ , so infinitely many values of $k=(2^r+2^s)/2$ make $2k+1$ special. Hence $f(k)$ increases without bound. Since it starts at $0$ and changes only by $0$ or $1$ , it assumes every positive integer.