Drop of Chaos (Constructing a Minimally Aperiodic Sequence)
Retina, 86 bytes - 5 = 81

$
_
(r`^(?&lt;-2&gt;.)+_((.)+)\b$
$1!
\b$
0
3#
#
0#
1
1#
2
2#
3
)r`\1(?&lt;-2&gt;.)*((.)+)$
$0#
!
&lt;empty&gt;


Where &lt;empty&gt; represents an empty trailing line. You can run the above code from a single file with the -s flag.

The input should be given in unary, e.g. 111111. I haven't tested it for output on the order of thousands yet - two of the regexes might get a bit slow after a while - but it can easily handle a couple of hundred in a few seconds.

Explanation

This is a simple backtracking solution.


Append a 0.
While the current sequence is invalid, remove all trailing 3s and increment the last non-3.
Repeat until we have a valid sequence of the desired length.


This backtracking is implemented by a loop of regex substitutions which aborts once the string remains unchanged through one iteration.

$
_


This appends a _ to the input, which is used to separate the unary input from the sequence we're building.

(r`^(?&lt;-2&gt;.)+_((.)+)\b$
$1!


This is the first substitution in the loop (indicated by the leading ().  The regex matches if a) there is a word character (i.e. a digit) at the end the string (which means the string is valid - we'll see below that invalid sequences are marked with a trailing #) and b) there are at least as many characters in the sequence as in the input (this is checked using balancing groups). If that's the case, we remove the input and append a !. This ! serves to make all regexes in the loop fail, such that it terminates.

\b$
0


If there is a word character at the end (i.e. the sequence is valid, and the loop wasn't terminated by the previous step), append a 0.

3#
#


If (instead) the sequence had been marked invalid and ended in 3, we remove that 3 (but leave the sequence as invalid, because there's no possible continuation for the current prefix... so the next character needs to be backtracked as well).

0#
1
1#
2
2#
3


If the sequence is marked invalid and any digit other than 3 is at the end, we increment the digit and remove the marker.

)r`\1(?&lt;-2&gt;.)*((.)+)$
$0#


The last substitution in the loop (as indicated by the )). It checks whether the string ends in ABA (where B is not longer than A but potentially empty). The relative lengths of A and B are again checked using balancing groups, and the repetition of A is checked with a simple backreference.

If this regex matches, we mark the sequence invalid by appending #.

!
&lt;empty&gt;


Once the loop terminates, all we need to do is remove the ! and are then left with the desired output.