a_n = c x \phi (a_{n-1}) , is bounded

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

w

17 users

TOPICS

No tags match your search

M

No tags match your search

M

a_n = c x \phi (a_{n-1}) , is bounded

G H J

Reveal topic tags

Euler s Phi Function

L

G H BBookmark kLocked kLocked NReply

Source: (2021-) 2022 XV 15th Dürer Math Competition Finals Day 1 E+1

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

30653 posts

#1 h Nov 29, 2022, 1:16 PM

Y by

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$ .

This post has been edited 3 times. Last edited by parmenides51, Dec 12, 2022, 5:54 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

9045 posts

#2 h Nov 29, 2022, 3:45 PM • 1 Y

Y by PRMOisTheHardestExam

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

8877 posts

#3 h Dec 25, 2023, 8:02 PM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

polishedhardwoodtable

130 posts

polishedhardwoodtable

#4 h Dec 25, 2023, 11:33 PM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

684 posts

#5 h Apr 26, 2025, 4:35 AM

Y by

Clearly, $m = 2, 3$ both work.

Let $p$ be greatest prime factor of $m.$ Clearly, all primes dividing $a_n$ must be less than $p.$ We have that $\frac{a_n}{a_{n - 1}} \geq m \cdot \prod_{p_i \leq p}\frac{p_i - 1}{p_i} > m \cdot \frac12 \cdot \frac23 \cdot \frac34 \cdot\dots\cdot\frac{p - 1}{p} = \frac cp \geq 1$ .

This post has been edited 1 time. Last edited by Ilikeminecraft, Apr 26, 2025, 4:36 AM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a