Avoidance Sequence

Terms $a_{0}$ to $a_{19}$ are $1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 22, 30, 41, 50, 61, 70, 81, 90, 111$ .

After this, a pattern emerges: terms $a_{20}$ to $a_{27}$ are $200, 311, 400, 511, 600, 711, 800, 911$ ; terms $a_{28}$ to $a_{35}$ are $2000, 3111, 4000, 5111, 6000, 7111, 8000, 9111$ ; and so on, so that $1$ more digit is added for every $8$ terms.

Using $\frac{1}{8}$ as a slope (since $1$ digit is added every $8$ terms), and $(20, 3)$ as a point (since $a_{20}$ has $3$ digits), and the floor function (since the number of digits must be an integer), we can relate the the number of digits $d$ and the $n^{th}$ term by the function $d = \lfloor \frac{1}{8}n + \frac{1}{2} \rfloor$ for $n \geq 20$ .

Therefore, $a_{2018}$ would have $d = \lfloor \frac{1}{8} \cdot 2018 + \frac{1}{2} \rfloor = \boxed{252}$ digits.

Initially, it looked like this was something that could be solved through exploration, so I wrote a Python program to find solutions that matched the examples provided.

def share_digits(a, b):
    # are any of the digits in a shared by b?
    x = set(str(a))
    y = set(str(b))
    return x & y

results = [0]
i = 1
limit = 45

while i < limit:
    new = previous = results[i - 1]

    while share_digits(new, previous):
        new += 1

    results.append(new)
    print(i, new)
    i += 1

However, after running it for a couple seconds it became abundantly clear that it would take a very long time to reach 2018.

1 1
2 2
3 3
...
19 111
20 200
21 311
22 400
23 511
24 600
25 711
26 800
27 911
28 2000
29 3111
30 4000
31 5111
32 6000
33 7111
34 8000
35 9111
36 20000

But a pattern became visible after around 36 iterations. By inspecting the length of the digits compared to their position in the result, we can see that $\text{num\_digits(i)} \approx \frac{i}{8}$ . Using this information, we see that $\frac{2018}{8} \approx 252$

The subsequence $(a_{8k+2})$ for $k=3, 4, 5, 6, \dots$ is $a_{26}=800,\ a_{34}=8000,\ a_{42}=80000,\ a_{50}=800000, \dots$

Notice that for each value of $k$ , the term in the subsequence has $k$ digits.

Solving for $k$ in $8k+2 = 2018$ gives $k=252$ . Therefore from the subsequence above, $a_{2018}$ would have $\boxed{252}$ digits.

I wrote a program to solve it. You don't need to use arrays because only the first 2 digits matters, and the other digits are just the same as the second digit.

int find_digit(int start, int avoid1, int avoid2) {
  for (int dig = start; dig <= 9; ++dig) {
     if (dig != avoid1 && dig != avoid2) return dig;
   }
  return -1;
}

void main(void) {
  // Let's start from a10.
  int digits = 2;
  int first_dig = 1;
  int second_dig = 0;
  int prev_first_dig;
  int prev_second_dig;
  for (int a = 11; a <= 2018; ++a) {
    prev_first_dig = first_dig;
    prev_second_dig = second_dig;
    first_dig = find_digit(prev_first_dig + 1, prev_first_dig, prev_second_dig);
    if (first_dig < 0) {
      ++ digits;
      first_dig = find_digit(1, prev_first_dig, prev_second_dig);
    }
    second_dig = find_digit(0, prev_first_dig, prev_second_dig);
    printf("First 2 digits of a%d: %d%d, total digits: %d\n", a, first_dig, second_dig, digits);
  }
}

Output:

First 2 digits of a2018: 80, total digits: 252.