\documentclass[11pt]{scrartcl}
\usepackage{evan}
\begin{document}
\title{SMO 2020/1}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 28}
\maketitle
\section*{Problem}
The sequence of positive integers $a_0, a_1, a_2, \dots$ is recursively defined
such that $a_0$ is not a power of $2$,
and for all nonnegative integers $n$:
\begin{enumerate}
\ii [(i)] if $a_n$ is even, then $a_{n+1}$
is the largest odd factor of $a_n$ and
\ii [(ii)] if $a_n$ is odd,
then $a_{n+1} = a_n + p^2$ where $p$
is the smallest prime factor of $a_n$.
\end{enumerate}
Prove that there exists some positive integer $M$
such that $a_{m+2} = a_m $ for all $m \geq M$.
\section*{Video}
\href{https://www.youtube.com/watch?v=yGeCeBOMyA4&list=PLi6h8GM1FA6yHh4gDk_ZYezmncU1EJUmZ}{\texttt{https://youtu.be/yGeCeBOMyA4}}
\newpage
\section*{Solution}
The sequence alternates even and odd,
so WLOG $a_1, a_3, \dots$ are the odd numbers.
Note that the sequence of smallest prime divisors
of $a_1$, $a_3$, \dots is a weakly decreasing sequence
and so it is eventually stable --- so
we may as well assume that $p \mid a_1, a_3, \dots$
and no term of the sequence isn't divisible by any smaller prime.
We consider two cases:
\begin{itemize}
\ii If eventually the sequence contains $p$ itself,
then in fact $p+1$ is a power of $2$,
and so if $a_{2k+1} = p$ then $a_{2k+3} = a_{2k+5} = \dots = p$.
\ii Otherwise, note that given $a_{2k+1} \neq p$ odd,
we have $a_{2k+3} \le \half(a_{2k+1} + p^2) \le a_{2k+1}$,
so the sequence of odd numbers is weakly decreasing.
Hence it stabilizes.
\end{itemize}
\end{document}