Competition problem — Number theory

Library / /23 of 140

Number theory Difficulty 4.6 AIME Prove it 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$ .

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$ .

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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.