Let $c \ge 2$ be a fixed integer. Let $a_1 = c$ and for all $n \ge 2$ let $a_n = c \cdot \phi (a_{n-1})$. What are the numbers $c$ for which sequence $(a_n)$ will be bounded? $\phi$ denotes Euler’s Phi Function, meaning that $\phi (n)$ gives the number of integers within the set $\{1, 2, . . . , n\}$ that are relative primes to $n$. We call a sequence $(x_n)$ bounded if there exist a constant $D$ such that $|x_n| < D$ for all positive integers $n$.
Problem
Source: (2021-) 2022 XV 15th Dürer Math Competition Finals Day 1 E+1
Tags: Euler s Phi Function, phi function, number theory, Sequence
29.11.2022 18:45
Since $a \mid b$ implies $\varphi(a) \mid \varphi(b)$ and $a_1 \mid a_2$, it is clear that $a_1 \mid a_2 \mid a_3 \mid \dots$. So the sequence is bounded iff it is eventually constant. In particular, then $c$ is of the form $\frac{N}{\varphi(N)}$ for some $N$. But it is easy to see that the only integer values of this form are $1,2$ and $3$. Indeed, if $N$ has prime factors $p_1<p_2<\dots<p_k$, this quotient is $\frac{p_1p_2\dots p_k}{(p_1-1)\dots (p_k-1)}$, so the denominator is divisible by $2^{k-1}$ and hence $k \le 2$. If $k=1$, then $c=\frac{p}{p-1}$ is an integer iff $p=2$ and hence $c=2$. If $k=2$, then $c=\frac{pq}{(p-1)(q-1)}$ has even denominator, hence must have $p=2$ and then $c=\frac{2q}{q-1}=2+\frac{2}{q-1}$ and hence $q=3$ and $c=3$. Finally, it is easy to check that for $c=2$ and $c=3$ the sequence becomes $2,2,2,\dots$ resp. $3,6,6,6,\dots$ and hence is indeed bounded.
25.12.2023 23:02
Answer is $c = 2$ and $c=3$ only, which obviously both work. Now assume $c \geq 4$, and let $p$ be the largest prime factor of $c$. Notice that the sequence $\{a_n\}$ can never contain any prime factor greater than $p$, hence we have $$\frac{a_n}{a_{n-1}} \geq c \cdot \prod_{p_1 \leq p} \frac{p_1-1}{p_1} > \frac 12 \cdot \frac 23 \cdots \frac{p_1-1}{p_1} = \frac c{p_1} \geq 1$$by a very obtuse bound. It follows $\{a_n\}$ will be unbounded.
26.12.2023 02:33
Notice if a number $a$ fails (as in, its sequence is unbounded) then any multiple $b$ of $a$ also fails because it is well known that if $a|b$ then $\phi(a)|\phi(b)$ and we can inductively show that $a_n|b_n$ for all $n$ (letting $a_n$ and $b_n$ be the terms of the sequences generated by $a$ and $b$ respectively.) Thus notice that $2$ and $3$ can be checked to work, but $4$, $6$, and $9$ can be shown to fail. Thus we can inductively show that all primes $p>4$ fail because $p-1$ contains either a previous prime larger than $4$ or one of the numbers $(4,6,9)$ as a factor (otherwise $p-1$ is at most $3$ contradiction) and thus all numbers containing a prime that isn't $2$ or $3$ in its prime factorization fails and then $4$ and $9$ failing show that only $2$ and $3$ work.