# olympic mathematics

For each integer $a_0 > 1$, define the sequence $a_0, a_1, a_2, \ldots$ by: $$a_{n+1} = \begin{cases} \sqrt{a_n}, & \mbox{if } \sqrt{a_n}\mbox{ is an integer,} \\a_n+3, &\mbox{otherwise,}\end{cases}$$ Determine all values of $a_0$ for which there is a number $A$ such that $a_n = A$ for infinitely many values of $n$.

I have figured that if there exists an $i$ such that $a_i \ \mathrm{mod}\, 3 = 2$, the elements after $a_i$ are all different. I think there are many ways to solve this question so i would appreciate any answers.

i think the answer is $a_0\ \mathrm{mod}\, 3 = 0$ but i can't prove it

examples: 7,10,13,16,4,2 doesn't work

3,6,9,3 works

please tell me if i can improve my question.

• $a_0=1$ works. $a_0 \equiv 2\mod 3$ does not (will never hit a square). $a_0\equiv 1 \mod 3;a_0 > 1$ will not work as it will hit a $(3m + 2)^2$ eventually. $a_0 \equiv 0 \mod 3$ will work as it will hit a $(3k)^2$ eventually which send it back to hit it again. – fleablood Jun 18 '18 at 17:13

## 2 Answers

There is no integer $a$ so that $a^2 \equiv 2 \mod 3$ (as $0^2 \equiv 0 \mod 3$, $1^2 \equiv 1 \mod 3$ and $2^2 \equiv 1 \mod 3$ so if $a_0\equiv 2 \mod 3$ then by induction $a_{i+1} = a_i + 3 \equiv a_0 \equiv 2 \mod 3$ and the sequence never repeats.

There are infinitely many squares that are multiples of $3$. The square roots of these are multiples of $3$. So $a_0 = 3k$ will eventually lead to a $a_n = (3m)^k$ so $a_{n+1} = 3m < a_n$ so $a_n$ will repeat infinitely. So any multiple of $3$ will be such a starting point.

(Obviously if a sequence repeats once it will, by induction, repeat infinitely many times.

This just means we must consider $a_0 \equiv 1 \mod 3$.

If $a_0 = 1$ then $a_1 = \sqrt 1 = 1$ so $a_0$ is such a starting point.

But $a_0 = 4 \implies a_1 = 2$ so $4$ is not a valid starting point.

If $a_0 = 7; a_1 = 10;a_2 = 13; a_3 = 16; a_4 = 4$ so $7$ iss not a valid starting point. Is any $1 + 3k$ other than $1$?

Well, it can't be less than $25$ as that will lead to $25$ which leads us to $5\equiv 2 \mod 3$. We need to be lead to a $(3k + 1)^2$ that leads to $3k + 1$ that does not lead to and $3k + 1 < (3m + 2)^2 < (3k+1)^2$.

Not sure any such number exists. $49$ for example is such that $7 < 16 < 49$ is a failure.

But if $(3k+1)^2> 49$ then $k > 2$ and $(3k-2)^2 = 9k^2 - 12k + 4 \ge 18k-12k +4 = 6k+ 4 > 3k + 1$ so $3k + 1 < (3k-2)^2 < (3k+1)^2$.

So there is no such $1 + 3k$ (other than $1$ that will work).

So $a_0 = 1$ and $a_0 = 3k$ are all such starting points.

• i think you have to prove that 3m is bigger than a0 – Chris2018 Jun 19 '18 at 23:13
• No need for that to be true. If $a_0=33$ say, then $a_1=36$, $a_2=6$, $a_3=9$ $a_4=3$ $a_5=6$ and we have an infinite loop all much less than $a_0$. – fleablood Jun 20 '18 at 5:26
• you're right im sorry. – Chris2018 Jun 20 '18 at 5:59

That only says you have a term $a_0$ in this sequence that generates a cycle.

$a^2=a+3$ means that $a=3k$ or $a=3k+1$

• For the case: $a_0=3k$

Try with $a_0=6$, $a_1=a+3=9$, $a_2=3$, $a_3=6$. for infinite values of $k$, $a_k$ is cyclic.

All terms of this sort would map to this small circle, because the distance of leapback is incomparably large in relation of the incremental value which is $3$, let's denote $3k$ is the starting edge $a_0$, at some extent $a_n$ would be written as $3(3x^2)$ by incrementing repeatedly its following terms, the draw back of this sequence is evaluated to $3x(3x-1)$ for larger values of $x$ this is estimated to be very big comparingly to the incremental constant and should override the edge $3k$ where it finally leads straight to the limited 3 steps cycle.

This python code shows my conjecture:

for i in range(1000000):
s=3*i
while(s!=0 and s!=3 and s!=6 and s!=9):
if (sqrt(s)==int(sqrt(s))):
s=sqrt(s)
else:
s=s+3
print i


The loop will never halt for all $3k$ terms tested up to 3 millions.

• For the case $3k+1$ it's trickier to prove since there is a small exception when $\sqrt{a}$ is a square itself where the oddity occurs.
• This is a hint, not a full answer. – Yves Daoust Jun 18 '18 at 8:07
• My bad i made a mistake – Abr001am Jun 18 '18 at 9:25