Sequence of integers where no $3$ are in arithmetic progression I'm having some trouble understanding some parts of this proof.  Specifically


*

*Why does missing the number $2$ in the ternary system avoid $3$ terms from being in arithmetic progression?  I read elsewhere that it was because if you did have $3$ numbers in arithmetic progression then writing those numbers in ternary would give a constant difference, $c$ with the last term being $1$, and this only occurs when the three terms each have last terms $0$, $1$ and $2$.  But I was a bit confused with that explanation.  Could you explain why a term with $2$ in the ternary representation of a number in the sequence is a sufficient condition for the existence of an arithmetic progression?

*Where specifically is the "greedy algorithm" applied?

*And just general clarification on what's going on in this proof would be helpful.


Thanks!



 A: Partial answer to "Why does missing the number 2 in the ternary system avoid 3 terms from being in arithmetic progression? " in detail.
Let $a, a + k, a + 2k$ be three terms in arithmetic sequence.
Let $k_i$ be the first non-zero ternary digit have $k$.  Let $a_i$ the corresponding digit of $a$.  Then corresponding $i$th digit of $a + k$ and $a + 2k$ are equivalent to $a_i + k_i \mod 3$ and $a_i + 2k_i \mod 3$.
If $k_i = 1$ then $a_i\mod 3, a_i + 1\mod 3, a_i + 2\mod  3$ are three different residues $\mod 3$ so one of them is $2$ (and one of them is $0$ and one of them is $1$.
Likewise if $k_i = 2$ then $a_i \mod 3, a_i + 2\mod 3$, and $a_i + 2*k\equiv a_i + 1 \mod 3$ are also so that one of them is $2$.
So if any three have terms are in arithmetic progression there will be a digit $2$.

Could you explain why a term with 2 in the ternary representation of a number in the sequence is a sufficient condition for the existence of an arithmetic progression?

It is not a sufficient condition for an arithmetic progression; it is a necessary condition.   So a lack of a $2$ is a sufficient condition to there not being any arithmetic progressions.
....
So if we list all the numbers that avoid any $2$s in their ternary representation we will get in ternary, the sequence $0, 1, 10,11, 100, 101......$ (which, irrelevantly in decimal, are: $0, 1,3,4,9,10,......$).  
No in ternary $100,000_{10} = 12002011201_3$  so we can make this sequence go up to $11111111111_3=88573_{10}$ which has $11111111111_2 = 2047$ terms.  
So we can easily make a sequence have $1983$ terms.  i.e. then $1983$th term would be $a_{1983_{10}} = a_{11110111111_2} = 11110111111_3=87844$.
So the answer is: Yes, we can do it.  $0,1,3,4,9,10,12,13,27,......, 87844$ is such a sequence.

"Where specifically is the "greedy algorithm" applied?"

I'm not entirely sure.  But I think the strategy of trying to find the "tightest" sequence is the general idea.
