For any positive integer $x$, we set $$ g(x) = \text{ largest odd divisor of } x, $$$$ f(x) = \begin{cases} \frac{x}{2} + \frac{x}{g(x)} & \text{ if } x \text{ is even;} \\ 2^{\frac{x+1}{2}} & \text{ if } x \text{ is odd.} \end{cases} $$ Consider the sequence $(x_n)_{n \in \mathbb{N}}$ defined by $x_1 = 1$, $x_{n + 1} = f(x_n)$. Show that the integer $2018$ appears in this sequence, determine the least integer $n$ such that $x_n = 2018$, and determine whether $n$ is unique or not.
Problem
Source: 2018 Pan-African Mathematics Olympiad
Tags: algebra, number theory, Sequence
WizardMath
03.07.2018 22:28
It's easy to see using induction that the general term of the series is $$a_n = 2^{\lfloor \sqrt{2n + \frac{1}{4}} - \frac{1}{2} \rfloor + \frac{1}{2} \cdot \lfloor \sqrt{2n + \frac{1}{4}} - \frac{1}{2} \rfloor \cdot \lfloor \sqrt{2n + \frac{1}{4}} + \frac{1}{2} \rfloor - n} \cdot \left( 2n - \lfloor \sqrt{2n + \frac{1}{4}} - \frac{1}{2} \rfloor \cdot \lfloor \sqrt{2n + \frac{1}{4}} + \frac{1}{2} \rfloor + 1 \right)$$ This basically says that when we express the elements in an array of the form $$\begin{array}{cccc} a_1,\\ a_2, & a_3\\ a_4, & a_5, & a_6\\ \vdots & \vdots & \vdots \\ a_{\frac{n(n+1)}{2}+1}, & a_{\frac{n(n+1)}{2}+2}, &\cdots , & a_{\frac{n(n+1)}{2}+n}\end{array}$$ We get this : $$\begin{array}{cccc} 2^0 \cdot 1,\\ 2^1 \cdot 1, & 2^0 \cdot 3\\ 2^2 \cdot 1, & 2^1 \cdot 3, & 2^0 \cdot 5\\ \vdots & \vdots & \vdots \\ 2^n \cdot 1, & 2^{n-1} \cdot 3, &\cdots , & 2^0 \cdot (2n-1) \end{array}$$ So $2018$ appears once, and exactly once in the sequence.
eisirrational
15.09.2018 09:14
I'm surprised no one has brought this up yet, but this problem is nearly an exact repeat of this ISL 1992 problem.
Did2
20.09.2018 09:35
What's the value of the least integer $n$?