Goutham wrote: Let $(a_n )_{n\ge 1}$ be a sequence of integers that satisfies \[a_n = a_{n-1} -\text{min}(a_{n-2} , a_{n-3} )\] for all $n \ge 4$. Prove that for every positive integer $k$, there is an $n$ such that $a_n$ is divisible by $3^k$ . I maybe missing some simple argument but this seems only a hard work question to me. Note that if we prove that if we start with three numbers not divisible by $3$, reduce everything modulo $3$, we get three consecutive zeros, then we can induct. IMHO, It is really easy(but terribly tedious) to brute force every initial configuration, along with the initial orderings to see that they all give three consecutive zeros in the end. I've tried for some and have succeeded up to a limit, but gave up because it was really just brute forcing everything.

@Rijul saini I actually brute forced a few cases with a program and the majority of initial conditions never reduce to three numbers which are zero modulo 3 within 1000 terms.

dinoboy wrote: @Rijul saini I actually brute forced a few cases with a program and the majority of initial conditions never reduce to three numbers which are zero modulo 3 within 1000 terms. That's interesting. Maybe I took an initial condition not representative of the general situation. Which ones did you take?

Ok actually I found a typo in one my my expressions. It appears all sequences have all terms $0 \pmod{3}$ after 18 terms at maximum, but with the number of cases possible it's pretty infeasible to do that out by hand.

dinoboy wrote: Ok actually I found a typo in one my my expressions. It appears all sequences have all terms $0 \pmod{3}$ after 18 terms at maximum, but with the number of cases possible it's pretty infeasible to do that out by hand. Ah, I'm relieved that you had a typo, else I would have spent the whole day thinking what I missed out And btw, yeah, my point exactly. I mean, the proof is quite straightforward, and easy to carry out, but really tedious and just a matter of hard work really.

A minor optimisation that makes it feasible to actually brute force it(brings it down to only 27 cases). note if the initial sequence is all positive then as the sequence is decreasing while all 3 numbers are positive there must eventually be a negative number. Once the sequence is negative it must eventually have a positive. Once we have a positive number as the latest element (say nth element) followed by immediately by a negative number(n-1th element of the sequence) consider n+1th and n+2th elements as well. They must be positive and monotonically increasing. For an initial sequence that is not all positive. Then if the 3rd element is positive we have either 2nd, 3rd and 4th elements are positive. While if the 3rd element is negative either the 4th or 5th term must be positive or else we have 3rd 4th and 5th elements are all negative and it must eventually have a positive term after which we again have a monotonic increasing positive sequence. From here it suffices to check the mere 27 cases of positive monotonically increasing sequences mod 3.