\documentclass[11pt]{scrartcl}
\usepackage{evan}
\begin{document}
\title{Brazil 2015/3}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 54}
\maketitle
\section*{Problem}
Given a natural $n>1$ and its prime factorization
$n=p_1^{\alpha 1}p_2^{\alpha_2} \cdots p_k^{\alpha_k}$,
its \textit{false derived} is defined by
\[ f(n)=\alpha_1p_1^{\alpha_1-1}\alpha_2p_2^{\alpha_2-1} \dots \alpha_kp_k^{\alpha_k-1}. \]
Prove that there exist infinitely many naturals $n$ such that $f(n)=f(n-1)+1$.
\section*{Video}
\href{https://www.youtube.com/watch?v=IMMkiy8rZ9w&list=PLi6h8GM1FA6yHh4gDk_ZYezmncU1EJUmZ}{\texttt{https://youtu.be/IMMkiy8rZ9w}}
\newpage
\section*{Solution}
The idea behind the consttruction is as follows:
\begin{claim*}
Let $m$ be an integer and let
\begin{align*}
x &= 169 \cdot 78 m - 25 \\
y &= 27 \cdot 78 m - 4.
\end{align*}
If $x$ and $y$ are squarefree, then $27x = 169y+1$
and \[ f(27x) = f(169y) + 1. \]
\end{claim*}
\begin{proof}
Note that $3 \nmid x$ and $13 \nmid y$.
Then $f(27x) = 3 \cdot 3^2 = 27$
and $f(169y) = 2 \cdot 13 = 26$, as needed.
\end{proof}
Therefore, it is sufficient to show that there are infinitely
many integers $m$ for which $x$ and $y$ as defined above are squarefree.
Fix a large integer $M$ and consider choices of $m \in \{1, \dots, M\}$.
For each prime $p$, the number of $m$ for which $p^2 \mid x$
or $p^2 \mid y$ is at most $2\left\lceil \frac{M}{p^2} \right\rceil$,
and is zero if $p^2 > \max(x,y)$.
So, the total number of invalid choices of $m \in \{1, \dots, M\}$
is upper bounded by
\[ \sum_{p=5}^{O(\sqrt M)} 2\left\lceil \frac{M}{p^2} \right\rceil
< 2M \cdot \sum_{p \ge 5} \frac{1}{p^2} + O\left( \frac{\sqrt M}{\log M} \right)
< 0.99M \]
for large enough $M$.
This implies the result.
\end{document}