For positive intenger $n$, define $f(n)$: the smallest positive intenger that does not divide $n$. Consider sequence $(a_n): a_1=a_2=1, a_n=a_{f(n)}+1(n\geq3)$. For example, $a_3=a_2+1=2,a_4=a_3+1=3$. (a) Prove that there exists a positive intenger $C$, for any positive intenger $n$, $a_n\leq C$. (b) Are there positive intengers $M$ and $T$, satisfying that for any positive intenger $n\geq M$, $a_n=a_{n+T}$.
Problem
Source: 2019 China North MO
Tags: number theory
kaede
22.02.2020 15:25
Lemma A
For any positive integer $n\geq 3$, we have $f( n) \leq n-1$.
proofSuppose that $n\geq 3$.
Assume that $n-1\mid n$, then $n\leq 2$, impossible.
So we must have $f( n) \leq n-1$.
$\blacksquare $
Lemma B
For any positive integer $n$, $f( 6n)$ is not divisible by $6$.
proofAssume that $f( 6n)$ is divisible by $6$.
Let $a=\nu _{2}( 6n)$, $b=\nu _{3}( 6n)$, $c=\nu _{2}( f( 6n))$, and $d=\nu _{3}( f( 6n))$.
We must have $f( 6n) \leq \min\left( 2^{a+1} ,3^{b+1}\right)$, of course.
Assume that $c\leq a$, then $f( 6n) /2\nmid 6n$, impossible.
Assume that $d\leq b$, then $f( 6n) /3\nmid 6n$, impossible.
So we must have $f( 6n) \geq 2^{a+1} \cdotp 3^{b+1}$.
This contradicts that $f( 6n) \leq \min\left( 2^{a+1} ,3^{b+1}\right)$.
$\blacksquare $
We will prove that the following proposition is true :
Proposition
Let $r_{n}$ be non-negative integer less than $12$ such that $n\equiv r_{n}\bmod 12$.
For any integer $n\geq 3$, $a_{n} =\begin{cases}
2 & \text{when} \ n\ \text{is odd}\\
3 & \text{when} \ r_{n} \in \{2,4,8,10\}\\
4 & \text{when} \ r_{n} =6\\
3\ \text{or} \ 4 & \text{when} \ r_{n} =0
\end{cases}$
Proof
Suppose that $n\geq 3$.
If $n$ is odd, then $f( n) =2$, which implise $a_{n} =2$.
If $r_{n} \in \{2,4,8,10\}$, then $f( n) =3$, which implies $a_{n} =a_{3} +1=3$.
If $r_{n} =6$, then $f( n) =4$, which implise $a_{n} =a_{4} +1=4$.
If $a_{n} \geq 4$, then $n$ is divisible by $6$.
Assume that $a_{n} \leq 1$ for some $n\geq 3$.
Let $m=\min\{n\in \mathbb{N} |\ a_{n} \leq 1,n\geq 3\}$.
Then $a_{m} =a_{f( m)} +1$, and so $a_{f( m)} \leq 0$.
This contradicts the minimality of $m$.
(Since $a_{1} =a_{2} =1$, we have $f( m) \geq 3$)
So we have $a_{n} \geq 2$ for any $n\geq 3$.
Assume that $a_{n} \geq 5$ for some $n\geq 5$.
Let $s=\min\{n\in \mathbb{N} |\ a_{n} \geq 5\}$.
Since $a_{s} \geq 4$, $s$ is divisible by $6$.
On the other hand, $a_{s} =a_{f( s)} +1\geq 5$, which implise $a_{f( s)} \geq 4$.
So $f( s)$ is also divisible by $6$.
This is impossible because of Lemma B.
Suppose that $r_{n} =0$.
Since $f( n) \geq 5$, we have $a_{n} =a_{f( n)} +1\geq 3$.
Since $a_{n} \leq 4$, we must have $a_{n} =3,4$.
$\blacksquare $
(a) From the proposition, we must have $a_{n} \leq 4$.
Lemma C
If $f( n)$ is even, then $f( n) =2^{\nu _{2}( n) +1}$ .
proof of lemmaLet $a=\nu _{2}( n)$ and $b=\nu _{2}( f( n))$
We must have $f( n) \leq 2^{a+1}$, of course.
Assume that $b\leq a$, then $f( n) /2\nmid n$, impossible.
So we must have $f( n) =2^{a+1} =2^{\nu _{2}( n) +1}$.
Assume that there exists $( M,T) \in \mathbb{N}^{2}$ such that $a_{n+T} =a_{n}$ for all $n\geq M\geq 2$.
Let $v=\nu _{2}( T)$ and $q=\text{lcm}\left\{j\in \mathbb{N} ;\ j\ \text{is odd and} \ j< 2^{v+1}\right\}$.
Let $k\in \mathbb{N}$ such that $k$ is odd, $q\mid k$, and $kT >M$.
Then we can verify that $a_{kT} =4$ as follows:
Since $f( kT) =2^{v+1}$, $f( kT)$ is even, which implies $a_{f( kT)} \geq 3$.
So we must have $a_{kT} =a_{f( kT)} +1\geq 4$, and so $a_{kT} =4$.
We can take $m\in \mathbb{N}$ such that $2^{m} -1\nmid T$.
Let $r\in \mathbb{N}$ such that $2^{r} \cdot T >M$ and $r+v\geq m$.
Then we can verify that $a_{2^{r} T} =3$ as follows:
Assume that $f\left( 2^{r} T\right)$ is even, then $f\left( 2^{r} T\right) =2^{r+v+1}$ because of Lemma C.
Since $2^{m} -1\nmid T$, we have $f\left( 2^{r} T\right) \leq 2^{m} -1< 2^{r+v+1}$, impossible.
So we must have $f\left( 2^{r} T\right)$ is odd.
Therefore $a_{2^{r} T} =a_{f\left( 2^{r} T\right)} +1=3$.
However, we have $a_{2^{r} T} \neq a_{kT}$, which contradicts the assumption.
Hence there does not exist $( M,T) \in \mathbb{N}^{2}$ such that $a_{n+T} =a_{n}$ for all $n\geq M$.
$\blacksquare $