For an integer $a \ge 2$, denote by $\delta_(a) $ the second largest divisor of $a$. Let $(a_n)_{n\ge 1}$ be a sequence of integers such that $a_1 \ge 2$ and $$a_{n+1} = a_n + \delta_(a_n)$$for all $n \ge 1$. Prove that there exists a positive integer $k$ such that $a_k$ is divisible by $3^{2022}$.
Problem
Source: Switzerland - 2022 Swiss Final Round p5
Tags: number theory, recurrence relation, divisor
RagvaloD
17.11.2022 14:47
It is old problem If $a_1=2^m 3^n b$ where $(b,6)=1$ then $a_{2}=2^m 3^nb+ 2^{m-1}3^n b=2^{m-1}3^{n+1}b, a_3= 2^{m-2}3^{n+2}b,...a_{m}=3^{n+m}b$ and then $a_{m+1}=3^{n+m}b+3^{n+m-1}b=2^23^{n+m-1}b \to a_{m+2}=2*3^{n+m}b,a_{m+3}=3^{n+m+1}b$ and is we continue that we will have $a_{m+2k+1}=3^{n+m+k}b$ for every natural $k$
Basu_Dev
12.11.2024 13:44
We'll use induction on $i$ to prove that, $\exists$ $a_k$ such that $3^i \mid a_k$ .
Base case : $i=1$
$$ a_{n+1} = a_{n} + \frac{a_{n}}{p}$$where $p$ is the smallest prime divisor of $a_n$.
If $a_n$ is odd then $a_{n+1}$ is even, then;
$$a_{n+2} = a_{n+1} + \frac{a_{n+1}}{2}$$$$\implies a_{n+2} = \frac{3 a_{n+1}}{2}$$
Here, $3 \mid a_{n+2}$ .
If $a_n$ is even then,
$$ a_{n+1} = \frac{3a_n}{2}$$Again, $3 \mid a_{n+1}$ .
---
Inductive Hypothesis : Assume $\exists$ $a_k$ such that $3^i \mid a_k$
We'd like to prove there exists $a_{z}$ such that $3^{i+1} \mid a_z$ .
$$a_{k+1} = a_{k} + \frac{a_{k}}{p}$$If $a_k$ is even then;
$$a_{k+1} = \frac{3a_k}{2}$$$$\implies \nu_3(a_{k+1}) = \nu_3(3a_k)-\nu_3(2) = \nu_3(3^{i+1}W) = \nu_3(3^{i+1}) + \nu_3(W) \ge i+1$$
Now, if $a_k$ is odd then;
$$a_{k+1} = a_k + \frac{a_k}{3}$$$$a_{k+1} = \frac{4a_k}{3}$$$$\implies \nu_2(a_{k+1}) \ge 2, \quad \nu_3(a_{k+1}) \ge i-1$$Now,
$$a_{k+2} = a_{k+1} + \frac{a_{k+1}}{2}$$$$a_{k+2} = \frac{3a_{k+1}}{2}$$$$\implies \nu_3(a_{k+2}) \ge i, \quad \nu_2(a_{k+2}) \ge 1$$Since, $a_{k+2}$ is still even
$$a_{k+3} = \frac{3a_{k+2}}{2}$$$$\implies \nu_3(a_{k+3}) \ge i+1$$Done.
AshAuktober
02.12.2024 11:16
Okay, this is nice! We prove that if $\exists k : \nu_3(a_k) = m, $ then $\exists l : \nu_3(a_l) \ge m+1$. Let $a_k = 3^xy$ where $gcd(y, 3)= 1$. If $y$ is even, then $l = k+1$ works. So assume $y$ is odd. Then $a_{k+2} = 3^x \times \left( \frac{y+3}{2} \right ) = 3^x y_1$. Since $y_1$ is odd (else we're done), we must have $y \equiv 3 \pmod{4}$. But now $y_1 \equiv 3 \pmod{4} \implies y \equiv 3 \pmod{8}$. Continuing simiarly, $v_2{y-3} = \infty \implies y = 3$, a contradiction. So indeed such an $l$ exists. But now we just induct and we're done.