Powers of 2

Let the sum of $f(n)$ be $S$ . We note that every $n$ contributes at least $1$ to $S$ , if $n$ a multiple of $2$ it contributes an extra $1$ , a multiple of $4$ , extra $2$ , ... a multiple of of $2^k$ contributes an extra $2^{k-1}$ to $S$ . Therefore, $S$ is given by:

$\begin{aligned} S(n) & = \sum_{i=1}^n f(i) \\ & = n + \left \lfloor \frac{n}{2} \right \rfloor + 2 \left \lfloor \frac{n}{4} \right \rfloor + 4 \left \lfloor \frac{n}{8} \right \rfloor + ... \\ \Rightarrow S(n) & = n + \sum_{j=1}^m \left(\left(2^j-2^{j-1}\right) \left \lfloor \frac{n}{2^j} \right \rfloor \right) \end{aligned}$

For a power of $2$ , $n=2^k$ :

$\begin{aligned}\Rightarrow S(2^k) & = 2^k + \left \lfloor \frac{2^k}{2} \right \rfloor + 2 \left \lfloor \frac{2^k}{4} \right \rfloor + 4 \left \lfloor \frac{2^k}{8} \right \rfloor + ... + 2^{k-1} \left \lfloor \frac{2^k}{2^k} \right \rfloor \\ & = 2^k + 2^{k-1} + 2^{k-1} + 2^{k-1} + ... + 2^{k-1} \\ & = (k+2)2^{k-1} \end{aligned}$

Since $S(2^7) = 576 < 1000 < S(2^8) = 1280 \quad \Rightarrow 2^7 = 128 < n < 2^8 = 256$ .

Estimate $n = \dfrac{1280}{256}\times 1000 = 200$

\(\begin{array} {} S(200) = 200 + 100 + 2(50)+4(25)+8(12)+16(6)+32(3)+64(1) = 852 \\ S(240) = 240 + 120 + 120 +120+120+112+96+64 = 992 \\ S(244) = 244 + 122 + 122 +120+120+112+96+64 = 1000 \end{array} \)

Therefore, $n = \boxed{244}$

$$

$\color{#3D99F6}{\text{FURTHER SOLUTION}}$

All $S(n)$ can be expressed as a sum of $S(2^k)$ as follows:

$\begin{aligned} \quad \quad S(n) & = b_0 S(2^0) + b_1 S(2^1) + b_3 S(2^3) + ... + b_m S(2^m) \\ & = \sum_{k=0}^m b_kS(2^k) \\ & = \sum_{k=0}^m b_k (k+2)2^{k-1} \end{aligned}$

where $b_k = 0$ or $1$ is a unit function or binary digit.

Then $n$ is given by:

$\begin{aligned} \quad \quad n_{10} & = (\overline{b_m...b_2b_1b_0})_2 \\ & = b_02^0 + b_12^1 + b_22^2 +...+ b_m2^m \\ & = \sum_{k=0}^m b_k 2^k \end{aligned}$

For $S(n) = 1000$ ,

$\begin{aligned} \quad \quad S(n) & = 1000 \\ & = 576 + 256 + 112 + 48 + 8 \\ & = S(2^7) + S(2^6) + S(2^5) +S(2^4) +S(2^2) \\ \Rightarrow n_{10} & = 11110100_2 \\ & = 128 + 64+32+16+4 \\ & = \boxed{244} \end{aligned}$

Construct the function $f$ from the prime factor decompositions of successive natural numbers, where possible. Then accumulate these values until 1000 is achieved.

But we don't need the full prime factor decomposition, just the greatest power of two! Here's a more economical way of getting the result.