Define a sequence as follows:
f(0) = 0
f(1) = 1
f(n) = least integer greater than f(n-1) that does not make an arithmetic progression with any two previous members of the sequence.
This sequence starts off like this: 0, 1, 3, 4, 9, 10, 12, ...
What is f(4100)?
The sequence continues:
Note that when n is a power of 2, f(n) is a power of 3. This gives us a clue! We claim that f(n) is related to n as follows: write n in base 2, and interpret the result in base 3 to get f(n). For example, n = 11 = 10112, and 10113 = 31 = f(11). As a result, the sequence contains all numbers which have all digits equal to 0 or 1 when written in base 3.
We prove this by induction. The claim is that the first n members of the sequence consist of the first n non-negative integers consisting entirely of digits 0 and 1 when written in base 3. It's clearly true for n = 1. Assume that it's true for the case n = k. and let a0, a1, ..., ak be the first k non-negative integers consisting entirely of digits 0 and 1 when written in base 3.
Suppose that the next possible number in the sequence, ak+1 contains some 2 digits when written in base 3. In this case, we have an arithmetic sequence immediately, since the numbers with digits 0 and 1 in those positions are previous members.So let ak+1 be the next number greater than ak which doesn't contain a digit 2 when written in base 3. We claim that it doesn't make an arithmetic sequence with any previous members. To see this, suppose it does make an arithmetic sequence (r, s, t) = (r, r+k, r+2k), with ak+1 = t, and common difference k. Here, r and s are previous members of the sequence, and therefore contain no 2's when written in base 3, by the inductive hypothesis. The next number t also does not contain any 2's, since we've already dealt with that case.
If the common difference contains only 1's and 0's, then the positions where it has a 1 must match the positions where r has a 0, since otherwise s would have a 2 in that position. But that means that t will have a 2 in that position, so this case is not possible.
As a result, k must have at least one 2 when written in base 3. Let i the lowest position where k has a 2. Then r must have a 1 in position i, since otherwise s would have a 2 in that position. Furthermore, all lower positions in r, s and k are 0's or 1's. Now consider position i in t. The value is 1 in r, 2 in k, and 0 in s. Furthermore, the numbers formed from positions i-1 to 0 in s and k are less than 3i/2, since they contain only 0's and 1's, so there can't be any carry over into position i when s and k are added. Therefore, t must have the digit 2 in position i. This contradicts the definition of t, and proves that there can't be an arithmetic sequence (r, s, t).
So, to find f(4100), we write it in base 2 as 4096 + 4 = 212 + 22 = 10000000001002, and interpret that as 10000000001003 = 312 + 32 = 531441 + 9 = 531450.