# A Never-Before-Seen Sequence

Continue the following sequence of a's, b's, and c's:

abcacbaabbccaaccbbabacabcbcaaabaacbbbcbabbacccacaabccbcbbcababcaacaccabbbaaacccbacbccccaaaabbabbcbcb


These are the first 100 letters in an infinite sequence. Every character is the best possible character to create a novel, never-before-seen sequence, for your puzzling enjoyment! And if by some odd coincidence you have seen it before, I hope it was as far in the past as possible.

Can you figure out the rule behind this sequence, and describe how to continue it indefinitely?

Hints will be given if a few days if needed, and feel free to post partial progress.

I think I got it! The answer is

given as the following Python code:

target = 'abcacbaabbccaaccbbabacabcbcaaabaacbbbcbabbacccacaabccbcbbcababcaacaccabbbaaacccbacbccccaaaabbabbcbcb'
s = 'abc'
for i in range(3, len(target)):
cur_best = (1e9, 1e9, '')
for c in 'abc':
s2 = s + c
for l in range(1, len(s2)): # identify the length of shortest unseen suffix
if s2[-l:] not in s: break
dup = s2[-l+1:] # longest seen suffix
app = s.rfind(dup) # its last appearance
cur_best = min(cur_best, (l, app, c)) # choose shorter unseen suffix,
# with earlier last appearance as the tiebreaker
s += cur_best[2]
print(s)
assert s == target[:len(s)]


Ever[y] character is the best possible character to create a novel, never-before-seen sequence...

Out of abc, the character that forms the shortest suffix that is unseen yet is chosen.

For example, after abcacba, aa is unseen but both ab and ac are already seen, so a is chosen.

And if by some odd coincidence you have seen it before, I hope it was as far in the past as possible.

If there are ties, find the suffixes that are 1 character shorter than the unseen suffix. Choose the one that has the earliest last appearance.

For example, after abcacbaabbcca,

• all of aa, ab, ac are seen.
• cac is seen, but caa and cab are not, so the candidates are a and b.
• The last appearance of aa is earlier than that of ab, so a is chosen.

Since this ruleset uniquely chooses one of abc at every step, the sequence can go forever with the given rules.

• Well done! Nicely solved and nicely explained, and good job figuring out the clues! Commented Aug 6 at 15:49