The sequence $a_1,a_2,a_3\ldots $, consisting of natural numbers, is defined by the rule: \[a_{n+1}=a_{n}+2t(n)\] for every natural number $n$, where $t(n)$ is the number of the different divisors of $n$ (including $1$ and $n$). Is it possible that two consecutive members of the sequence are squares of natural numbers?
Problem
Source: Bulgarian National Olympiad 2012 Problem 1
Tags: number theory proposed, number theory
SCP
21.05.2012 22:27
Obivouls it can't, cause $t(x^2)$ is odd, so by mod 4 solved.
kroki
22.05.2012 09:25
SCP wrote: Obivouls it can't, cause $t(x^2)$ is odd, so by mod 4 solved. Well, I actually meant "is it possible that there exists a natural number k, such that $a_{n}$ and $a_{n+1}$ are squares of natural numbers". Also note that we have t(n), not t($a_{n}$).
SCP
22.05.2012 21:02
Excuse me for my fault. Just remark $t(n)< 2 \sqrt{n}+1$ and $a_n \ge 2n-1 \ge n$, so $t(n)< (\sqrt{a_n}+1)^2-a_n.$ Hence $t_n$ can't be the difference of the two consecutive squares.
yunxiu
23.05.2012 04:41
SCP wrote: Excuse me for my fault. Just remark $t(n)< 2 \sqrt{n}+1$ and $a_n \ge 2n-1 \ge n$, so $t(n)< (\sqrt{a_n}+1)^2-a_n.$ Hence $t_n$ can't be the difference of the two consecutive squares. So ${a_{n + 1}} - {a_n}=2t(n)< (\sqrt{a_n}+2)^2-a_n$, as ${a_{n + 1}} \equiv {a_n}(\bmod 2)$ Hence ${a_n},{a_{n + 1}}$ can't be two squares.
Assassino9931
25.08.2022 00:22
Pretty much as a problem from Balkan MO Shortlist 2012 (the Balkan olympiad was held a few days before the Bulgarian National Olympiad actually).
Assassino9931
19.11.2024 17:29
Note that the sequence is strictly increasing, in particular $a_n \geq n$ for all $n$. Suppose that $a_n = m^2$. Since $a_{n+1} > a_n$ and $a_{n+1}$ and $a_n$ have the same parity, we obtain $a_{n+1} \geq (m+2)^2$. Hence \[ 4m+4 \leq a_{n+1} - a_n = 2\tau(n) \leq 4\sqrt{n} \leq 4m \]contradiction.