Let $d(n)$ denote the number of positive divisors of $n$. For any given integer $a \geq 3$, define a sequence $\{a_i\}_{i=0}^\infty$ satisfying $a_{0}=a$, and $a_{n+1}=a_{n}+(-1)^{n} d(a_{n})$ for each integer $n \geq 0$. For example, if $a=275$, the sequence would be \[275, \overline{281,279,285,277,279,273}.\] Prove that for each positive integer $k$ there exists a positive integer $N$ such that if such a sequence has period $2k$ and all terms of the sequence are greater than $N$ then all terms of the sequence have the same parity. Proposed by Navid
Problem
Source: 2024 IRN-SGP-TWN Friendly Math Competition P2
Tags: number theory, divisor function
sami1618
02.08.2024 20:25
We will use the fact that for all $\epsilon >0$ then $d(n)=\mathcal{O}(n^{\epsilon})$. This implies that for all big numbers $B$ we can choose a $N$ such that $$d(n)\leq \frac{\sqrt{n}}{B}$$for all $N\leq n$. The key observation is that $a_i$ only changes sign at a perfect square. If we choose $B$ large enough we can guarantee that the $a_i$ will only stay in a range that contains one perfect square. Assume that the sequence changed signs. At most one term in the period can be equal to a perfect square. But the sequence must clearly change signs at least twice in a period, a contradiction.
math_comb01
02.08.2024 20:34
Notice that it suffices to show the following statement; Rephrased Problem wrote: If a big enough perfect square appears in the sequence, then period is odd FTSOC assume it's even then there must exist even number of perfect squares in the period because perfect squares change the parity, however we can easily prevent that by using the well known fact that we can choose a $N$ such that $k \cdot d(n) \leq \sqrt{n}$ for big $k$, (see a proof here), contradiction. done
jp62
04.08.2024 08:07
Notice that $d(n)$ is odd iff $n$ is a perfect square, so if not all the terms of the sequence have the same parity, then there must be a square number. Suppose that $a_m=x^2$ is the first square number in the sequence, and consider the next square number (which exists by periodicity). $a_{m+1}$ is a different parity from $a_m$ and $a_i$ has the same parity until the next square is encountered, so the next square must have different parity from $a_m$. Thus there must exist at least two distinct squares in the sequence. Now we show that if all terms are $>N$, then this cannot hold.
Where $n=\prod_{p_i}p_i^{\alpha_i}$, $$\frac{d(n)}{n^\varepsilon}=\prod_{p_i}\frac{1+\alpha_i}{p_i^{\varepsilon\alpha_i}}$$and for primes $p_i$ such that $p_i^\varepsilon\geq e$ we have $$\frac{1+\alpha_i}{p_i^{\varepsilon\alpha_i}}\leq\frac{1+\alpha_i}{e^{\alpha_i}}\leq \frac{e^{\alpha_i}}{e^{\alpha_i}}=1$$and for the other finitely primes the quantity $\frac{1+x}{p_i^{\varepsilon x}}$ is bounded in $x$.
Multiplying these together we get $\frac{d(n)}{n^\varepsilon}$ is bounded as desired.
that $d(n)=O(n^\varepsilon)$ for any $\varepsilon>0$, we can find $N_1$ such that $d(n)<n^{\frac14}$ for all $n>N_1$. We can also find $N_2$ and $N_3$ such that $n^2+2k\sqrt{n+1}<(n+1)^2$ for all $n>N_2$ and $n^2-2k\sqrt{n+1}>(n-1)^2$ for all $n>N_3$. Now choose $N>N_1$ and $\sqrt{N}>N_2,N_3$. We can show by induction that $a_{m+i}$ lies in the range $[x^2-i\sqrt{x+1},x^2+i\sqrt{x+1}]$ for $0\leq i\leq 2k$ with base case $i=0$. By choice of $N_2$ we have $a_{m+i}<(x+1)^2$ and $a_{m+i}>N$ by assumption, so $d(a_{m+i})<a_{m+i}^{\frac14}<\sqrt{x+1}$ and thus proving the statement for $a_{m+i+1}$. Finally, by periodicity, the entire sequence is contained in $[x^2-2k\sqrt{x+1},x^2+2k\sqrt{x+1}]$, which contains no other square numbers by choice of $N_2$ and $N_3$.
navid
05.08.2024 02:55
We considered it as an Algebra problem, however it needed several ideas from Number Theory. The participants did really well in solving it.