# Sequence of integers where no $3$ are in arithmetic progression

I'm having some trouble understanding some parts of this proof. Specifically

1. 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?
2. Where specifically is the "greedy algorithm" applied?
3. And just general clarification on what's going on in this proof would be helpful.

Thanks!

• "Why does missing the number 2 in the ternary system avoid 3 terms from being in arithmetic progression?" $a,a +k, a + 2k$ will require a digit of two. Take the first non zero ternary digit of $k$. Then that digit of $a, a+k,$ and $a + 2k$ will be all three possible values. Commented Jun 29, 2018 at 19:22
• I think the greedy algorithm occurs in that it is assumed that making as "tight" a sequence and starting as low as you can will allow you to "fit" in the longest possible sequence then starting higher and having some loose selection. Commented Jun 29, 2018 at 19:42
• "And just general clarification on what's going on in this proof would be helpful." THis isn't a proof. It's a solution. The answer, (surprisingly) is YES, you CAN find 1983 terms in which no three are in arithmetic progression. Just list the numbers without any twos in their ternary representation. Commented Jun 29, 2018 at 19:44

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.