Who could have thought Sophie germain primes give you such a relief if you know what I mean Kudos to the guy who managed to latex the sol

To prove that he can reach the number $2$ from anywhere, and can reach anywhere from the number $2.$ For $n>2,\tau(n)$ is always smaller than $n,$ because $n$ is not divisible by $n-1.$ After finite applications of $\tau(n),$ he will get $2.$ Probably soon enough, because he just needs a prime, since $\tau(\mathrm {prime})=2.$ For any $2^n,$ $\tau(2^n)=n+1$ $\sigma(2^n)=2^{n+1}-1$ $\phi(2^n)=2^{n-1} $ Any odd $k,$ integer $n\ge 0$ $\tau(k*2^n)=(n+1)\tau(k)$ $\sigma(k*2^n)=(2^{n+1}-1)\sigma(k)$ $\phi(k*2^n)=2^{n-1}*\phi(k)$ And any number is $k*2^n $ in unique way.$2^n=n+1$ $\sigma(2^n)=2^{n+1}-1$ $\phi(2^n)=2^{n-1} $

The following 9 steps solve the problem:

Solution with Superguy MarkBcc168 wrote: For any positive integer $n$, let $\tau(n)$ denote the number of positive integer divisors of $n$, $\sigma(n)$ denote the sum of the positive integer divisors of $n$, and $\varphi(n)$ denote the number of positive integers less than or equal to $n$ that are relatively prime to $n$. Let $a,b > 1$ be integers. Brandon has a calculator with three buttons that replace the integer $n$ currently displayed with $\tau(n)$, $\sigma(n)$, or $\varphi(n)$, respectively. Prove that if the calculator currently displays $a$, then Brandon can make the calculator display $b$ after a finite (possibly empty) sequence of button presses. Proposed by Jaedon Whyte. WLOG assume $a=2.$ Call a number obtainable if by some compositions of the discussed arithmetic functions we can obtain it. Let $S$ be the net of obtainable numbers. Clearly we will be done if we can obtain all powers of two (just apply $\tau$). The main idea is to understand $\varphi.$ Note that $\nu_2(\varphi(n))<\nu_2(n)$ if and only if $n$ is a power of two and if $\nu_2(\varphi(n))=\nu_2(n)$ then $n=2^aq^m$ where $q$ is some odd prime. Hence by composing $\varphi$ many times on $n$ we can obtain $2^{\nu_2(n)}.$ Assume the contrary that $\nu_2$ of all the numbers in $S$ is bounded. Note that $\omega(n)$ is bounded above for all $n\in S$ otherwise we will get a large $\nu_2$ by applying $\varphi$ ($\omega(n)$ is the number of distinct prime factors of $n$). And all the exponents in the prime factorisation is also bounded since otherwise by applying $\varphi$ many times so that powers of $2$ appear in the exponents and then finally $\tau$ we will get numbers with high $\nu_2.$ Let $M$ be the largest possible $\nu_2$ from the obtainable numbers. Clearly, these numbers would be of the form $2^Mp$ where $p=1$ or $p$ is a member of some long sequence of Sophie-Germain primes, because if we keep on applying $\varphi$ the $\nu_2$ shouldn't increase. Clearly the length of this sequence of Sophie-Germain primes is bounded above by a constant since the largest member of this sequence would be something like $2^kp+2^k-1$ so if we apply $\sigma$ we get a large $\nu_2.$ Hence what we do is that, keep applying $\sigma$ till we get a very large number. Suppose we get a large number $N.$ Now this number will have large prime factors and bounded exponents, we keep applying $\varphi,$ since we wouldn't encounter Sophie-Germain sequences any soon, the $\nu_2$ of the number will get very large. And we are done. $\blacksquare$

Interesting fact: From any positive integer $k$ larger than $(2^n+n) \uparrow \uparrow (2^n+n)$ (where we use Knuth's up arrow notation), we can reach $n$ from $k$ by using only the $\phi$ and $\tau$ functions with at most two uses of the $\tau$ function. Thus, in place of the $\sigma$ function we could have had any other function which allows us to reach arbitrarily large numbers from $2$.

Mathotsav wrote: Interesting fact: From any positive integer $k$ larger than $(2^n+n) \uparrow \uparrow (2^n+n)$ (where we use Knuth's up arrow notation), we can reach $n$ from $k$ by using only the $\phi$ and $\tau$ functions with at most two uses of the $\tau$ function. Thus, in place of the $\sigma$ function we could have had any other function which allows us to reach arbitrarily large numbers from $2$. Do you have a proof?

redacted, fakesolve

@above your solution doesn't work. The $\sigma\left(n_i\right)$ is multiplicative only if all the $n_i$ are relativily prime

Proposer Comment: It is actually possible to show that at most $2^{b+2}$ button presses are needed to reach $b$ from $2$. However, this version was of course dropped from the test for being a bit ridiculous.

Another way to complete the problem with an idea similar to #4 is the following: Let $\Omega(n) = \sum e_i$, where $n =\prod p_i^{e_i}$. Claim. For every positive integer $k$, there is a bound $N_k$ such that if $n \ge N_k$, then at least one number $x$ in the sequence $n, \varphi(n), \varphi(\varphi(n)),...$ has $\Omega(x) \ge k$. A sketch of an induction (in $k$) proof is the following: 1. Reduce to the case $n=p$ is prime. 2. See that the only case in which we cannot (easily) use the induction hypotesis is the one in which $p$, $\frac{p-1}{2}$, $\frac{\frac{p-1}{2}-1}{2}$,... is a "large" sequence of Sophie-Germain primes. 3. Bound such sequences by assuming that the claim doesn't work for $k$ and using the bound $N_{k-1}$.

(Solution with niyu) This problem is actually pretty detail-heavy. The Latex writeup towards the end is pretty bad because of this, as I grew somewhat bored of writing all the steps. Edit: Looking at other solutions it seems like this solution is needlessly complicated; not the question itself We first state two (known?) easy to prove claims about the function $\phi$ Claim 1: $v_p(\phi(n)) + 1 \ge v_p(n)$ Claim 2: $v_2(\phi(n)) \ge v_2(n)$ unless $n$ is a power of $2$ Optimization 1: We're done if we reach a number $n$ divisible by $2^b$ Proof: Keep on applying $\phi$ to $n$ untill we reach a power of $2$, say $2^k$. By Claim 2, $k>b$ and we can continue applying $\phi$ we eventually reach $2^b$. Now $\tau(2^b) = b$ Optimization 2: We're done if we reach a number which has $b+1$ distinct prime divisors Proof: An application of $\phi$ followed by optimization 1 Optimization 3: There exists some $k$ (in particular, $2^b$ suffices), such that we're done if we reach a number divisible by $p^k$ for any prime $p$ Proof: Keep on applying $\phi$ to the number. By claim 1 and discrete continuity, we eventually have a number $n$ such that $v_p(n) = 2^b-1$ Optimization 1 finishes after we note that $v_2(\tau(n)) \ge b$ We now assume for the sake of contradiction, that we cannot reach $b$ Optimization 4: If we can somehow reach a number $n = \prod p_i^{\alpha_i}$, then $\sum \alpha_i$ is bounded This follows from Optimizations 2 and 3 Now, we try to overwhelm the reader with a barrage of notation; Call a prime $p$ semi-evil if $\frac{p-1}{2}$ is also a prime Call a number of the form $2^s3^t$ an endstate For a number $n = \prod p_i^{\alpha_i}$, we define $f(n) = \sum \alpha_i$ [$f(n)$ is number of prime factors of $n$ with multiplicity] Lemma: Unless $n$ is an endstate $f(\phi(n)) \ge f(n)$ Proof: If $m$ and $h$ are coprime, $f(\phi(h)) + f(\phi(m)) - f(m) - f(h) = f(\phi(ab)) - f(ab)$ Let $n = mh$ where $h$ is an endstate. It is easy to see that $f(\phi(m)) - f(m) \ge 1$ and $f(\phi(h)) - f(h) = -1$ The only equality case is when $f(\phi(m)) - f(m) = 1$ or when $m$ is a semi-evil prime We now define the step sequence $s_1, s_2, \cdots$ as follows $s_1 = 2020$ $s_{i+1}$ is defined based on $s_i$ recursively Consider all primes $p < s_i$, and try to trace the sequence $2p+1, 4p+3, 8p+7 \cdots$ and stop as soon as you reach a number that isn't prime. This sequence is guaranteed to be finite as $2^{p-1}p + 2^{p-1} - 1$ appears in this sequence and is divisible by $p$. The largest number you've written so far is $s_{i+1}$ Also for convenience, if according to this, $s_{i+1} < 2^{s_i}$, we instead set $s_{i+1} = 2^{s_i}$ Now, the worth of a prime $p$ is defined as the largest $i$ such that $p > s_i$ Let $g(n)$ denote the worth of the largest prime that divides $n$ Problem Finish: Literally everything that follows will just be a way to get around large Sophie-Germaine sequences We can use $\sigma$ to generate arbitrarily large numbers. [In fact, we could just replace $\sigma$ by a large number generator] Get some number $n$. Consider the sequence $n_1, n_2, \cdots$ where $n_1 = n$ and $n_{i+1} = \phi(n_i)$ and stop the sequence when you reach an endstate. Now the key idea is to consider the monovariant $m_i = 4f(n_i) + g(n_i)$ Our claim is that given some $n_i$ we can always pick $j>i$ and $m_j \ge m_i$ We break this into two parts Decrease the first part of the monovariant by at most $1$ but ensure that there is non-semi-evil prime dividing $n_j$ whose worth is $g(n_j)$ To do this, observe that if the largest prime $p|n_k$ is semi evil and we apply $\phi$, we get the prime $\frac{p-1}{2}$ dividing the next term of the sequence. As we track this prime and what it spawns, we eventually reach a non semi-evil prime. By definition of step sequence, the worth has not decreased by more than $1$ By the lemma, $f(n)$ Some bounding, when there is a large non-semi-evil prime Let the non-evil-prime be $p$ and let $f(\phi(p)) = q+1, q\ge 2$. Let largest prime dividing $\phi(p)$ be $r$. We have the following bounds: \[ 2r^q \ge p \]\[ r \ge \underbrace{\ln \cdots \ln}_{q \text{times}} p \]This means that worth$(p) - $worth$(r) \le q+2$ Thus the monovariant increases by at least $1$, since $f(n)$ increases by $q-1$ and $g(n)$ decreases by at most $q+1$ Since eventually the worth is really small, by the time we reach an endstate, the sum of exponents will be high, since the worth is $0$. Now by optimization 4, we're done.

Here's a full writeup of the solution outlined in Gomes17's post above. (Mathotsav also found this solution during the contest.) The details aren't that bad, actually. Define $T(n)$ to be the total number of prime divisors of $n$, counting multiplicity. Observe that $T(\varphi(n)) \ge T(n)$ for all $n$ except those of the form $2^\alpha 3^\beta$. Also, for a prime $p$, define $f(p)$ to be the first composite term in the sequence $(\varphi^i(p)/2)_{i \ge 1}$ or $2$ if no composite term exists. For example, $f(47) = 2$ since $23, 11, 5$ are prime. Claim: Let $C$ be an integer. For all primes $p$ sufficiently large, $f(p) > C$. Proof: Suppose otherwise; then $f(p)=s$ infinitely often. Equivalently, $2s+1, 4s+3, \dots, 2^m(s+1)-1, \dots$ are all prime. But this is false if we take $m=2s+1$ whence $2^m(s+1)-1$ vanishes mod $2s+1$. $\Box$ Claim: Let $C$ be an integer. For all primes $p$ sufficiently large, there is $i \ge 1$ with $T(\varphi^i(p)) \ge C$. Proof: We induct on $C$, the base case $C=1$ being trivial. Suppose it holds for $C$ and let $q$ be the largest prime for which $\max_{i \ge 1} T(\varphi^i(q)) \le C-1$. Using Claim 1, select $p$ with $f(p) > q^{C+1}$. Suppose all prime divisors of $f(p)$ are at most $q$. Then $T(2f(p)) \ge C+1$ and we win. Suppose $f(p)$ has a prime divisor $r > q$. In other words, applying $\varphi$ many times to $p$ yields $2f(p) = 2rk$ for some $k>1$. By hypothesis, $T(\varphi^j(r)) \ge C$. So, as $\varphi^j(r) \mid \varphi^j(2rk)$, we have $T(\varphi^j(2rk)) \ge C$. We wish to show that equality cannot hold, i.e. $\varphi^j(r) \neq \varphi^j(2rk)$. Indeed, they are not equal if $j=1$ due to $k$, and if $j$ larger, they are not equal because $m$ even, $m \neq n$, and $m \mid n$ implies $\varphi(m) \neq \varphi(n)$. This completes the induction. $\Box$ It's not hard to extend Claim 2 to all sufficiently large integers $N$ instead of primes: either $N$ has a working prime factor $p$ and we win because $\varphi^i(p) \mid \varphi^i(N)$, or $N$ has at least $C$ small prime factors. Now we solve the problem at hand. Let $k$ denote our current number, $k=a$ to start. By the above observation, we can apply $\sigma$ until $T(\varphi^i(k)) \ge 2^b + b$ for some $i$. Then, apply $\varphi$ many times until just before $T$ starts decreasing. At this point, $k$ must be of the form $2^\alpha 3^\beta$, where $\alpha + \beta \ge 2^b + b$. If $\alpha \ge b$, then $\nu_2(k) \ge b$ and we win by applying $\varphi$ until $k=2^{b-1}$ and finally applying $\tau$. Otherwise, $\beta \ge 2^b$. In that case apply $\varphi$ until $\nu_3(k) = 2^{b-1}-1$, apply $\tau$, and finish as before. This concludes the proof.

Let $S$ be the set of all the numbers we can reach by the three operations, starting from any arbitrary integer Claim 1: If $S$ contains numbers divisible by arbitrarily large powers of $2$, then $S=\mathbb{N}$ Notice that $\phi (n)<n$ and $v_2(\phi(n))\leq v_2(n)$ unless $n$ is a power of two. With this in mind, take $k\in S$ such that $2^m|k$. Repeat $\phi$ on $k$ until it becomes a power of $2$ (which by the first two conclusions must happen) and then repeat $\phi$ until it becomes $2^m$. Now take $\tau (2^m)=m+1$ and do this for every $m$ $\square$ Claim 2: If arbitrarily large powers of $p$, a prime, divide elements of $S$, then $S=\mathbb{N}$ Case 1: $p>3$ Suppose $p$ doesn't divide $n$, and $np^a\in S$ such that it's $v_2$ is maximum for $a\geq 2$. Then $\phi (np^a)= \phi (n) p^{a-1}(p-1)$ is also in $S$, and it's $v_2$ is higher then $v_2(np^a)$ unless $n$ is a power of $2$. But if it is, $v_2(\phi (\phi (np^a)))$ is obviously higher (by some casework, here $p$ can't be $3$), a contradiction. This means there are arbitrarily large powers of $2$ dividing the elements of $S$, so we are done by claim $1$. Case 2: $p=3$ Here we also use case $1$, suppose the degrees of all the other primes dividing elements of $S$ are $\leq M$. Again, take $n\in S$ with the biggest $v_2$ such that $3^a$ divides it (a\geq 2). Then $v_2(\phi(n))>v_2(n)$ unless $n$ is of the form $2^x3^y$. But then we can achieve $2^x3^z$ for all $z<y$, and take $\sigma (n) = (2^{x+1}-1)\frac{1}{2}(3^{z+1}-1)$. By LTE lemma we can obviously make it's $v_2$ arbitrarily large, so we are again done by claim $1$ $\square$ For every $n$, define $\omega (n)$ to be the sum of the degrees of all the primes dividing it Claim 3: $\omega (n)\leq L$ for all $n\in S$, or $S=\mathbb{N}$ If $\omega$ is not bounded in $S$, by claim $2$ there must be integers in $S$ with arbitrarily many different prime divisors. Taking $\phi$ of such a number we obviously get an arbitrarily big powers of $2$ dividing an element in $S$, so we are done by claim $1$ again. Final claim: $S$ has to be $\mathbb{N}$ anyways Because $\sigma (n)>n$, obviously $|S|=\infty$. Because of that, and $\omega (n\in S) \leq L$, there is some $k$ such that $\omega (n\in S)=k$ for infinitely many such $n$, and take the largest such $k$. We use the fact that $\phi (n)\geq \frac{\sqrt{n}}{2}$, or anything that bounds $\phi$ below. This means if we take a large enough $n\in S$ with $\omega (n)=k$, then $\omega$ of $\phi (n)$ and $\phi( \phi (n))$ is $\leq k$ (because we took $k$ maximal). This is untrue, however, unless $n$ is of the form $2^a3^bp$ where $\frac{p-1}{2}$ is also prime (easy by some casework). But by taking $n$ large enough, we can apply $\phi$ more times without it getting too small (i.e. stay bigger then all the members of $S$ with their $\omega$ bigger then $k$). To simplify, take $f(n)=\frac{n-1}{2}$ This means there exist primes $p$ which divide some $n\in S$, and with $f^i(p)$ being prime for $i$ arbitrarily large. Doing $f$ "backwards" in a sense, we get that $p = 2^iq+2^i-1$ for a prime $q$. But $p+1$ divides $\sigma$ of that $n$ (remember that the power of $p$ dividing $n$ is $1$), and $2^i|p+1$, so once again, we are done by claim $1$

This is from post 5.

Does this work? It doesn't use Sophie Germain primes at all and actually uses a property of $\sigma$ other than the fact that it increases the written number. Obviously Brandon can repeatedly apply $\tau$ to turn $a$ into $2$, so it suffices that he can reach any positive integer (other than $1$) from $2$. Call the numbers that he can reach reachable (duh). Because $\tau(2^k)=k+1$, it suffices to show that he can reach every power of $2$. Because $\varphi(2^k)=2^{k-1}$, it suffices to show that he can reach arbitrarily large powers of $2$. Because applying $\varphi(n)$ to a number decreases its $\nu_p$ by at most $1$, decreases its $\nu_2$ only when it's a power of $2$, and repeatedly doing so eventually sends its $\nu_p$ to $0$ (where $p$ is any fixed prime), it suffices to show that we can reach numbers with arbitrarily large $\nu_2$. Furthermore, if we cannot reach such numbers, then the $\nu_p$ of any reachable number must be bounded: otherwise, by "discrete continuity" repeated applications of $\varphi$ to a number with large $\nu_p$ will result in a number whose $\nu_p$ is equal to $2^k-1$ for large $k$, and then using $\tau$ will give us arbitrarily large powers of $2$. Therefore, suppose for contradiction that the $\nu_p$ of any reachable number must be bounded for any prime $p$ (this boundedness is not "per-prime" but rather "universal", but it doesn't really matter). Suppose we start at an arbitrary reachable number $n$ and repeatedly apply $\varphi$ until the number displayed is either of the form $2^i3^j$, $2^ip$ where $p \neq 3$ is an odd prime, or $2^i$, at which point we immediately stop. Consider the $\nu_2$ of the displayed number $m$. Every time we apply $\varphi$, view this $\nu_2$ as decreasing by at most $1$ (exactly $1$ if $2 \mid m$ and $0$ otherwise), then increasing by some number $l$. This application of $\varphi$ decreases the written number by a factor of at most $2^{l+1}$. If we end up applying $\varphi$ a total number of $k$ times, it follows that the resulting factor is smaller than $n$ by a factor of at most $2^{k+\sum l}$, where the sum is across all the $l$ in each step. On the other hand, its $\nu_2$ is at least $-k+\sum l$. We now have the following key claim. Claim: $l$ cannot equal $1$ for two consecutive applications of $\varphi$. Proof: Suppose that for some operation $m \to \varphi(m)$ we have $l=1$. Since $m$ is not of the form $2^i3^j,2^ip,2^i$, it has exactly one odd prime divisor $p$ without multiplicity, which is $3 \pmod{4}$ and not equal to $3$, i.e. $m=2^ip^j$ for some $j>1$. But since $p \neq 3$, $\tfrac{p-1}{2}$ is divisible by some odd prime $q$, so now $\varphi(m)$ is divisible by at least two distinct odd primes (namely $p,q$), hence for $\varphi(m)$ we have $l \geq 2$. $\blacksquare$ This implies that, due to our assumption on the boundedness of $i$, we must have $2^{k+\sum l}$ bounded, since $\sum l \geq 1.5k-1000$. Since the $\nu_p$ of any reachable number is bounded, $i$ and $j$ are bounded. On the other hand, since repeatedly applying $\sigma$ generates arbitrarily large numbers, it follows that arbitrarily large numbers are reachable. For large enough reachable $n$, repeated applications of $\varphi$ starting from $n$ must therefore result in a number of the form $2^ip_n$ for some prime $p_n>3$. Since $i$ is still bounded and we want $\frac{2^ip_n}{n}$ to be bounded below by some positive number (since this quantity is at least $\frac{1}{2^{k+\sum l}}$ which we assume is bounded below), it follows that $\frac{n}{p_n}$ is bounded above. Let $f(n)$ denote the largest prime divisor of $n \neq 1$. Since $p_n \leq f(n)$, it follows that $\frac{n}{f(n)}$ is bounded above as well across all sufficiently large reachable $n$, hence bounded above across all $n$. Suppose this is the case. Since $f(n) \mid n$, suppose that $a \in \mathbb{Z}^+$ is maximal such that there exist infinitely many $n$ with $\frac{n}{f(n)}=a$, and let $S$ be the set of all such $n$. For large enough $n$, $f(n)$ should grow arbitrarily large, hence far larger than $a$. It follows for these $n$ that $\sigma(n)=(f(n)+1)\sigma(a)$. But its largest prime divisor is at most $\max\{\frac{f(n)+1}{2},\sigma(a)\}$, so for large enough $n$ we have $f(\sigma(n)) \leq \frac{f(n)+1}{2}$, implying $\frac{\sigma(n)}{f(\sigma(n))} \geq 2\sigma(a)>a$: contradiction. Hence no such $a$ exists and $\frac{n}{f(n)}$ is unbounded above, contradicting our original assumptions and finishing the problem. $\blacksquare$