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 5 of 5: Count the corresponding unique values

Previous step Next step

In plain words

Count the corresponding unique values

m=\dfrac{n(n-1)}2+1

Detailed analysis

The interval is $\{2^n+3,\ldots,2^{n+1}+4\}$ . Its three-one numbers are $2^n+2^r+2^s$ with $0\le r<s<n$ , giving $\binom n2=\frac{n(n-1)}2$ numbers, together with $2^{n+1}+3$ . Thus the unique values are exactly $m=\frac{n(n-1)}2+1$ for integers $n\ge2$ , namely $2,4,7,11,\ldots$ .