\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}
