olympic mathematics

Question

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.

Answer 1

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.

Answer 2

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.