Track / Stage 4 / 104 of 340 #844 of 2444

Problem 844

AMC 12 late, AIME early

Number theory Difficulty 4.6 Prove it Brazilian Mathematical Olympiad · Brazil

Let $f: \mathbb{Z}_{+}^{*} \rightarrow \mathbb{Z}_{+}^{*}$ be a function defined as follows: given $n$ , we write $n = 2^a \cdot (2b+1)$ , with $a$ and $b$ non-negative integers, and define $f(n) = a^2 + a + 1$ .

Determine the least positive integer $n$ such that $f(1) + f(2) + \cdots + f(n) \ge 123456$ .

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

Let $S_k = f(1) + f(2) + f(3) + \dots + f(2^k)$ . Then
$S_k = f(1) + f(2) + \dots + f(2^{k-1}) + f(1) + f(2) + \dots + f(2^{k-1} - 1) + f(2^k)$
$\Leftrightarrow S_k = 2S_{k-1} - f(2^{k-1}) + f(2^k)$
$\Leftrightarrow S_k = 2(S_{k-1} + k)$
If $n = (a_t a_{t-1} \dots a_0)_2$ is the binary expansion of $n$ , it is easy to see that $f(1) + \dots + f(n) = \sum a_i \cdot S_i$ . Also, by induction, $S_k > S_{k-1} + \dots + S_0$ , so that in order to obtain the least $n$ satisfying $f(1) + \dots + f(n) \ge 123456$ , we have to choose
$S_{14} + S_{13} + S_7 + S_2 + S_1 = 123456,$
that is, $n = 2^{14} + 2^{13} + 2^7 + 2^2 + 2^1 = 24710$ .

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.